The sorting floor
A Socratic walk-through of the sorting floor — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why can no method that works by comparing pairs ever sort faster than a certain speed?
Most claims about algorithms are claims about one algorithm: this method takes this long. They are proved by exhibiting the method. But there is a claim about sorting that is stronger and stranger — that no method of a certain kind can beat a certain speed, including methods nobody has invented yet.
How could anyone possibly prove that? You cannot enumerate the future. So what is it about comparison-based sorting that lets us reason about every conceivable procedure at once?
Reasoning it through
REASONING #Start by asking what a sorting method that only compares elements actually knows. It never inspects a value's digits, never uses it as an index, never does arithmetic on it. Its sole source of information is questions of the form "does a come before b?", each answered yes or no.
So set the machinery aside and look only at the flow of information. Before the first question, what do you know about the input's arrangement? Nothing: any of the n! orderings of n distinct items is possible. And when you are finished and can name the sorted order, what do you know? Exactly one of them — you have identified the permutation. Sorting, seen this way, is not rearranging. It is identification: narrowing n! candidates to one.
Now, how much can a single yes-or-no answer narrow a set of candidates? At best, it splits it in half — one bit. And it can do no better than half, because the candidates consistent with "yes" and the candidates consistent with "no" together make up everything you had. So after k questions you have distinguished at most 2^k possibilities.
That is the whole argument. To identify one of n! arrangements you need 2^k to be at least n!, hence k at least log2(n!) comparisons — in the worst case, since no matter how the questions are chosen the adversary can always answer along the fatter branch.
The same thing said with a picture rather than with bits: trace any comparison sort as a tree. Each internal node is a comparison, each of its two edges is an answer, and each leaf is an output arrangement. Every one of the n! input arrangements must reach a distinct leaf — if two reached the same one the method would emit the same order for both and be wrong on at least one. A binary tree with n! leaves has height at least log2(n!). The height is the number of comparisons on the longest path, which is the worst case.
Then it is arithmetic. Stirling's approximation gives log2(n!) as roughly n log2 n minus 1.44n, which is n log2 n asymptotically. For a hundred items the floor is about 525 comparisons — no procedure that only compares pairs will ever sort a hundred items in 500, however cleverly written, however fast the machine.
Now the honest boundary. Radix sort and counting sort demonstrably run in linear time. Do they refute this? No — they violate the premise. Counting sort uses each key as an index into an array, which is not a comparison; it extracts far more than one bit per operation and pays for it by requiring keys drawn from a small known range. Radix sort does the same digit by digit. The theorem is not "sorting requires n log n"; it is "sorting by comparison alone requires n log n", and the escape hatch is to stop comparing.
One more caveat worth flagging, because it is where the theorem is most often overstated. The bound counts comparisons, not time, and it applies to the worst case. The average case is also n log n by a related argument about the tree's total path length, and randomization does not evade it either — a randomized method is a distribution over such trees, and its expected comparison count obeys the same floor. What is not covered: comparison sorts on partially ordered or nearly sorted input, where the candidate set is smaller than n! to begin with and adaptive methods legitimately do better.
The analogy
THE ANALOGY #Think of twenty questions. Your opponent has chosen one object from a list, you may ask only yes-or-no questions, and the list is a million items long. No amount of cleverness lets you finish in ten questions, because ten questions can distinguish at most 1,024 objects and you needed to distinguish a million. The limit has nothing to do with your strategy — it is a property of the questions you are permitted to ask.
twenty questions is a game against a fixed hidden answer, whereas a lower-bound proof assumes an adversary free to decide the answer as it goes, choosing whichever reply leaves the larger set of candidates alive — so the bound holds even against a sorter that got lucky, which the game does not capture.
Clarifying the model
THE MODEL #Two clarifications that repair the usual misreadings.
The first is that this is a statement about a model, not about the universe. "Comparison-based" is a restriction on what an algorithm may do with its inputs — it may order two of them and nothing else. Inside that model the bound is airtight and needs no unproven assumptions, which is rare: most lower bounds in complexity theory are conditional on conjectures like P not equalling NP. This one is unconditional precisely because the model is narrow. Every unconditional lower bound we have is bought this way.
The second is that log2(n!) is not a loose bound. Mergesort uses about n log2 n minus 1.44n comparisons in the worst case — matching the floor to within lower-order terms — so the floor is essentially achieved, not merely approached. The gap between what information theory permits and what a practical method delivers is, in this one happy case, almost nothing.
A picture of it
THE PICTURE #How to readthis is the decision tree for three items. Start at the root and take one branch per answer; every leaf is a distinct arrangement, and all six of the 3! arrangements must appear or the method would be wrong on one of them. Count the deepest path — three comparisons — and notice that no rearrangement of the questions can make the tree shallower than the number of leaves demands.
What became clearer
WHAT CLEARED #The floor is not a fact about sorting; it is a fact about counting. A sorter that may only ask ordering questions is an identification procedure gathering one bit at a time, and no procedure can distinguish more possibilities than its answers encode. Change what the algorithm is allowed to ask — let it use a key as an address — and the floor simply does not apply, which is the clearest sign that it was always a statement about the questions rather than about the task.
Where to go next
ONWARD #- Sorting networks and the still-open question of the exact minimum number of comparisons for small n, where the log2(n!) bound is known not to be tight.
- Adaptive sorting, where the measure of difficulty is the input's existing disorder rather than its length.
- Yao's minimax principle, the standard tool for extending worst-case lower bounds to randomized algorithms.
Key terms
TERMS #| Term | What it means |
|---|---|
| Comparison sort | a sorting method whose only access to the data is pairwise ordering queries. |
| Decision tree model | representing an algorithm as a binary tree of queries, with outputs at the leaves, in order to reason about all algorithms of that kind. |
| log2(n!) | the number of bits needed to name one arrangement of n items; about n log2 n minus 1.44n. |
| Unconditional lower bound | a limit proved outright, with no reliance on unproven conjectures, achievable only within a restricted model. |
Every term the collection defines is gathered in the glossary.