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(n*^{1+1/k} ˙ *(log n)*^{1+1/k}) processors, and that we can sort in *k* rounds if we have *O(n*^{1+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(n*^{1+1/k+o(1)}) processors. If we use randomized methods, then it is possible to sort using only *O(n*^{1+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.