Sorting in rounds (Q1117700)

The paper considers the number SORT(n,r) of parallel processors necessary to sort n elements in time r, in the case where \(r=r(n)\) is small compared to n. The author establishes an asymptotic upper bound \[ f(n,r):=2^{r+1} n^{1+1/r} (\log n)^{2-2/r} (\log \log n)^{-(r- 1)/r} \] for \(2\leq r(n)\leq \log \log \log n\). (Results by Ajtai et a. imply an upper bound SORT(n,r)\(\leq c n (\log n)/r\) for \(r\geq \log n)\). The probabilistic method is used to show the existence of an algorithm and explicit constructions of the graphs or estimates on the order of magnitude of the constants involved are not given. However, the author observes that the sorting networks only depend on n and r, and of course are independent of the ordering of the input.