Parallel sorting

AbstractWe show that if n is sufficiently large then there is a graph G of order n with ⌊n32logn⌋ edges such that the transitive closure of every acyclic orientation of G has at least n2−n32logn edges. A consequence of this is that with ⌊n32logn⌋ parallel processors n objects may be sorted in two time intervals. This improves considerably some results of Häggkvist and Hell. We prove similar assertions about sorting with only d-step implications