TAOCP 5.3.1 Exercise 23
The information-theoretic lower bound \(\lceil \lg n!
Section 5.3.1: Minimum-Comparison Sorting
Exercise 23. [10] The text proves that the average number of comparisons made by any sorting method for $n$ elements must be at least $\lceil \lg n! \rceil \approx n \lg n$. But multiple list insertion (Program 5.2.1M) takes only $O(n)$ units of time on the average. How can this be?
Verified: no
Solve time: 52s
The information-theoretic lower bound (\lceil \lg n! \rceil) on the average number of comparisons holds for any sorting algorithm that operates solely by comparing pairs of elements (i.e., comparison-based sorting). Multiple list insertion (Program 5.2.1M) is not a comparison-based algorithm: it uses the numerical values of the keys to compute indices into an array of lists (for example, by scaling a uniformly distributed key to a bucket number), thereby distributing elements into buckets in (O(1)) time per element. The total running time is (O(n)) on average because the algorithm performs (O(n)) non-comparison operations (arithmetic, list insertion, concatenation) and the number of key comparisons it makes is not the dominant factor; indeed, it may make no comparisons between keys at all. Hence the comparison-tree lower bound does not apply, and there is no contradiction.