Parallel Sorting with Constant Time for Comparisons

We prove that there exist graphs with n vertices and at most $2n^{5/3} \log n$ edges for which every acyclic orientation has in its transitive closure at least $\begin{pmatrix} n \\ 2 \end{pmatrix} - 10n^{5/3} $ arcs. We conclude that with $2n^{5/3} \log n$ parallel processors n items may be sorted with all comparisons arranged in two time intervals. We also show that $\frac{1}{9}n^{3/2} $ processors are not sufficient to achieve the same end. These results are extended to parallel sorting in k time intervals, and related to other work on parallel sorting. The existence of sorting algorithms achieving the bounds is proved by nonconstructive methods. (The constants quoted in the abstract are somewhat improved in the paper.)