Chapter notes

The decision-tree model for studying comparison sorts was introduced by Ford and Johnson [94]. Knuth's comprehensive treatise on sorting [185] covers many variations on the sorting problem, including the information-theoretic lower bound on the complexity of sorting given here. Lower bounds for sorting using generalizations of the decision-tree model were studied comprehensively by Ben-Or [36].

Knuth credits H. H. Seward with inventing counting sort in 1954, and also with the idea of combining counting sort with radix sort. Radix sorting starting with the least significant digit appears to be a folk algorithm widely used by operators of mechanical card-sorting machines. According to Knuth, the first published reference to the method is a 1929 document by L. J. Comrie describing punched-card equipment. Bucket sorting has been in use since 1956, when the basic idea was proposed by E. J. Isaac and R. C. Singleton.

Munro and Raman [229] give a stable sorting algorithm that performs O(n^1+∈) comparisons in the worst case, where 0 < ∈ ≤ 1 is any fixed constant. Although any of the O(n lg n)-time algorithms make fewer comparisons, the algorithm by Munro and Raman moves data only O(n) times and operates in place.

The case of sorting n b-bit integers in o(n lg n) time has been considered by many researchers. Several positive results have been obtained, each under slightly different assumptions about the model of computation and the restrictions placed on the algorithm. All the results assume that the computer memory is divided into addressable b-bit words. Fredman and Willard [99] introduced the fusion tree data structure and used it to sort n integers in O(n lg n/ lg lg n) time. This bound was later improved to time by Andersson [16]. These algorithms require the use of multiplication and several precomputed constants. Andersson, Hagerup, Nilsson, and Raman [17] have shown how to sort n integers in O(n lg lg n) time without using multiplication, but their method requires storage that can be unbounded in terms of n. Using multiplicative hashing, one can reduce the storage needed to O(n), but the O(n lg lg n) worst-case bound on the running time becomes an expected-time bound. Generalizing the exponential search trees of Andersson [16], Thorup [297] gave an O(n(lg lg n)²)-time sorting algorithm that does not use multiplication or randomization, and uses linear space. Combining these techniques with some new ideas, Han [137] improved the bound for sorting to O(n lg lg n lg lg lg n) time. Although these algorithms are important theoretical breakthroughs, they are all fairly complicated and at the present time seem unlikely to compete with existing sorting algorithms in practice.