Chapter notes

Knuth [185] contains a discussion of sorting networks and charts their history. They apparently were first explored in 1954 by P. N. Armstrong, R. J. Nelson, and D. J. O'Connor. In the early 1960's, K. E. Batcher discovered the first network capable of merging two sequences of n numbers in O(lg n) time. He used odd-even merging (see Problem 27-2), and he also showed how this technique could be used to sort n numbers in O(lg² n) time. Shortly afterward, he discovered an O(lg n)-depth bitonic sorter similar to the one presented in Section 27.3. Knuth attributes the zero-one principle to W. G. Bouricius (1954), who proved it in the context of decision trees.

For a long time, the question remained open as to whether a sorting network with depth O(lg n) exists. In 1983, the answer was shown to be a somewhat unsatisfying yes. The AKS sorting network (named after its developers, Ajtai, Komlós, and Szemerédi [11]) can sort n numbers in depth O(lg n) using O(n lg n) comparators. Unfortunately, the constants hidden by the O-notation are quite large (many thousands), and thus it cannot be considered practical.