Tight Comparison Bounds on the Complexity of Parallel Sorting
Yossi Azar, Uzi Vishkin · SIAM Journal on Computing · 1987
The problem of sorting n elements using p processors in a parallel comparison model is considered. Lower and upper bounds which imply that for $p \geqq n$, the time complexity of this problem is $\Theta ({ {\log n} / { \log ({ {1+p} / n }) } })$ are presented. This complements [AKS-83] in settling the problem since the AKS sorting network established that for $p \leqq n$ the time complexity is $\Theta ({{n\log n} / p})$. To prove the lower bounds we show that to achieve $k \leqq \log n$ parallel time, we need $\Omega (n^{{{1 + 1} / k}} )$ processors.