The sorting wall

Three cards lie face up, each with a different number. A comparison asks one yes-or-no question, such as whether the first card is smaller than the second. Six orders are possible: three choices for the first card, two for the second and one for the third, and that product is the factorial of three, written 3! and read "three factorial". For a whole number n, n! is the product of the numbers from 1 to n, so 3! is 6 and 4! is 24.

A comparison has two outcomes, so two comparisons distinguish at most four orders and three comparisons distinguish eight. No procedure that only compares pairs can sort three cards with fewer than three comparisons, and the same counting argument scales. !Three cards, six possible orders, and a tree of yes-or-no questions. Two comparisons reach four leaves and cannot name all six orders; three reach eight and can. Every comparison sort needs at least log base two of n! comparisons: 15.30 at eight items, so sixteen at the least, and merge sort uses seventeen. Status: schematic.

Why comparison sorting cannot beat n log₂ n is a count of the possible answers rather than a property of any particular algorithm. A comparison tree records the questions the procedure asks: each internal node is a comparison, and each leaf, a node with no children below it, is an order the procedure can output. The tree is binary, because every question has two answers, and its depth, the number of comparisons on the longest path from the root to a leaf, is the worst case for that procedure. A correct sort must be prepared for every one of the n! input orders, so it needs at least n! leaves.

The shape of that tree gives a lower bound, a statement that no procedure of the stated kind can do better. A binary tree with k leaves has depth at least log₂ k, because each level can at most double the number of leaves. Since a correct comparison sort needs at least n! leaves, some input forces at least log₂(n!) comparisons [S:11:241]. Here log₂(n!) is the logarithm base two of n factorial, the number of questions needed to name one order out of n! orders, since a depth of d can name at most two to the d orders. The bound holds under every comparison sort at once, not a verdict on one program.

Worked example. Count the orders and compare the bound with a procedure that comes close to it. The last column counts the comparisons used by merge sort, the procedure of the previous section that sorts each half and merges the two sorted halves.

The logarithm is rarely a whole number, and a comparison count is always whole, so the least number of comparisons is the ceiling of log₂(n!), the next whole number at or above it. At eight items the ceiling is 16 and the merge procedure of the previous section uses at most 17, which leaves a gap of one. At ten items the ceiling is 22 and the procedure uses at most 25, so the gap is still small and does not grow quickly.

The eight-item row is worth checking by hand, because two to the fifteenth power is 32,768, which is below 40,320, and two to the sixteenth is 65,536, which is above it. Sixteen comparisons are therefore enough to name one of the 40,320 orders and fifteen are not. The same check at four cards needs no calculator: two to the fourth power is 16, below 24, and doubling once more passes it, so five comparisons are enough and four are not. That is the whole content of the logarithm in this argument: it counts how many yes-or-no questions are needed to name one item from a list of n! possibilities.

$$C(n)\ge {\log }_2(n!)\approx n{\log }_{2}n-1.44n$$

The number of comparisons is at least the logarithm of the number of orders, which is about n log₂ n minus a term proportional to n. The 1.44 is log₂ e, the constant that Stirling's approximation leaves behind, and it depends on the base of the logarithm without changing the class.

Why must the tree have at least n! leaves? Suppose two different input orders led to the same leaf. The procedure would ask the same questions and reach the same conclusion on both, so it would output the same order for two different inputs, and at least one of them would be sorted wrongly. A correct procedure therefore needs a separate leaf for every input order, and the depth of the tree is the largest number of comparisons it can be forced to make.

The bound is a statement about information rather than about sorting, and it holds in the comparison model, the rules under which a procedure may inspect the keys only by comparing pairs. Naming one order out of n! distinct orders requires log₂(n!) yes-or-no answers, and each comparison supplies exactly one answer, so the count of comparisons cannot be smaller than the count of answers. The argument never mentions a programming language, a machine or a data structure, which is why it applies to every comparison sort at once.

A lower bound of this kind also tells you when to stop improving an algorithm. If a procedure is within a small factor of log₂(n!), no change inside the comparison model will remove that factor, and the only remaining gains are constants and machine effects.

The bound explains the wall in the chapter's question. A procedure that halves the problem at each step comes within a small factor of the bound, which is why n log n is the practical limit for sorting by comparisons. The gap between a second and a week appears when a procedure falls off the ladder to n².

The wall has a gate, and the gate is the word comparison. A procedure that reads the values themselves, rather than only comparing pairs, can sort in time proportional to n when the values are small whole numbers. Counting sort does exactly that: it counts how many times each value occurs, then writes the values out in order of their counts, so it never compares two keys [S:11:243]. The bound is also asymptotic, so it says nothing about the constants at small n, and it does not certify that any particular program is optimal. It rules out a whole family of methods at once, which is both its strength and its limit.

The formal statement. Fix $n$ and a deterministic comparison sort $A$ that sorts $n$ distinct keys. Run $A$ and record each comparison as a node with two children, one per outcome. The result is a binary tree whose internal nodes ask whether one key is smaller than another, and whose leaves are labelled by permutations [S:11:240]. Correctness needs at least $n!$ leaves, because two input orders that reach one leaf receive the same output, and at least one of them is then sorted wrongly. So the height is at least ${\log }_2(n!)$, and some input forces that many comparisons [S:11:241].

The derivation. The leaf count is the whole proof, and the height lemma is an induction. A binary tree of height $h$ has at most $2^h$ leaves, so a tree with $k$ leaves needs $h\ge \lceil {\log }_{2}k\rceil$. Stirling's approximation turns ${\log }_2(n!)$ into $n{\log }_{2}n-n{\log }_{2}e+O(\log n)$, which is $\Theta (n\log n)$. The constant $1.44$ in the core's display is ${\log }_{2}e$.

The edge case. Randomisation does not move the floor. Fix the random string and $A$ becomes deterministic, with its own tree. A random input selects a random leaf, and the expected depth of a random leaf in a tree with $k$ leaves is at least ${\log }_{2}k$ [S:11:242]. So the expected comparison count is also at least ${\log }_2(n!)$, and the bound covers every comparison sort, randomised ones included.

A second edge. The theorem assumes that the only operation on keys is a comparison. A procedure that reads a key and uses it as an index leaves the model. Radix sort sorts $n$ $w$-bit integers in $O((w/d)(n+2^d))$ time for any $d>0$ [S:11:246]. The wall belongs to the comparison model, and it is not a law about sorting in general.

What the core hid. The core stated the bound correctly and showed the gap to merge sort in its own table, so it hid neither the floor nor the gap. What it did not give is the induction on the height of the tree, the argument that carries the bound to randomised algorithms, and the statement that the bound restricts the comparison model rather than sorting itself. Those three do not change the number; they change what it applies to.

Where the wall breaks. A wall has one gate, and the gate here is the word comparison. Change the model and the wall disappears, as radix sort shows. The information reading has a second limit: the theorem counts leaves and needs no distribution over inputs, so weighting comparisons by probability gives a different, entropy-based bound rather than this one.

Original sources. The comparison lower bound has no single paper behind it. Open Data Structures says the lower bounds appear to be folklore, and attributes the algorithms instead: merge sort to von Neumann in 1945, quicksort to Hoare, and heapsort to Williams, with the linear-time heap construction due to Floyd [S:11:247]. The same argument appears in every algorithms text, which is why the credit goes to a community rather than to an author. The proof you read is the standard decision-tree argument, stated as Theorem 11.5 [S:11:241].

An open question. The floor is $\lceil {\log }_2(n!)\rceil$, and the field has not settled whether that floor is attainable for every $n$. Merge sort spends up to $n{\log }_{2}n-n+1$, which is above the floor, and the gap is a lower-order term. Evidence that would settle it: an explicit decision tree with exactly $\lceil {\log }_2(n!)\rceil$ leaves for each $n$, or a proof that some $n$ forbids one.

A frontier result. Radix sort leaves the comparison model and sorts $n$ $w$-bit integers in $O((w/d)(n+2^d))$ time for any $d>0$ [S:11:246]. The counting sort underneath it costs $O(n+2^d)$ per pass, which is where the $2^d$ enters. When the keys lie in the range from zero to $n^c-1$, the bound becomes $O(cn)$, which is linear in the number of keys [S:11:247]. The result matters here because it shows exactly what the lower bound assumes: keys that you may only compare.

What to read next. Read section 11.1.4 of Open Data Structures for the deterministic proof and the extension to randomised algorithms [S:11:242]. Read the radix-sort theorem in the same chapter for the change of model [S:11:246]. Keep the decision-tree picture; it is the object that every later lower bound in this book reuses.