It is well known that sorting a list of n elements is possible with O(n ˙ log n) comparisons. If we have several processors working in parallel, then we can sort n elements even faster. For example, if we have n(n-1)/2 processors, then we can make all the comparisons at once (that is, we can sort n elements in a single round of comparisons). It is possible to show that if we want to sort in one round, then we need at least n(n-1)/2 processors working in parallel. If we do not have that many processors, the next natural questions are: How many processors do we need to sort n elements in 2 rounds? In 3 rounds? In k rounds for a given value k? For this, it is known that we need at least O(n1+1/k ˙ (log n)1+1/k) processors, and that we can sort in k rounds if we have O(n1+1/k ˙ (log n)2-1/k) processors. The existence of such k-round sorting is proven nonconstructively, by showing that such a sorting must exist. If we restrict ourselves only to efficient (polynomial-time computable) sorting schemes, then the best known k-round sorting algorithms require slightly more, namely, O(n1+1/k+o(1)) processors. If we use randomized methods, then it is possible to sort using only O(n1+1/k) processors.
Gasarch, Golub, and Kruskal survey the existing lower and upper bounds and the corresponding algorithms, and they also provide an experimental comparison of different algorithms. The authors describe, for real n and k, which algorithms are empirically better. Some conclusions of their experimental analysis are as anticipated: factors of log log n do not usually affect the algorithm’s performance; more complex algorithms that are asymptotically better behave worse for small n. However, there is one somewhat unexpected conclusion: nonconstructive algorithms often perform as well as constructive ones, and sometimes even better. A reason for this may be that the existence theorems behind nonconstructive algorithms are usually proven by showing that almost all graphs with a certain property lead to fast sorting; so, we can often use random number generators to generate random graphs with these properties, and, in these cases, the graphs lead to well-performing sortings.
