A wall we have been circling
You have already met merge sort, which arranges n keys in O(n log n) time, and randomized quicksort, whose expected time is also O(n log n). It is natural to wonder: is that just the best anyone has thought of yet, or is it the genuine floor? This is precisely the question the previous guides taught us to take seriously — a lower bound on a problem is a statement about the task itself, holding against every present and future algorithm, not a confession about one method. This guide proves that for sorting by comparisons, n log n really is a wall.
Everything hinges on what we count, so we fix the rules first. In the comparison model, the only way an algorithm learns about the keys is by asking questions of the form "is a[i] <= a[j]?" and branching on the yes/no answer. It may not peek at the bits of a key, hash it, use it as an array index, or do arithmetic on it. Many beloved sorters — merge sort, quicksort, heapsort, insertion sort — obey exactly these rules, so a lower bound in this model speaks about all of them at once.
Every comparison sorter is a tree
The previous guide gave us the key instrument: the decision tree. Take any comparison sorter and run it on inputs of a fixed size n, drawing a node for each comparison it makes. Each internal node is a question "a[i] <= a[j]?" with two children, one for "yes" and one for "no". A particular input traces a single root-to-leaf path, answering each question along the way, and when the algorithm finally stops, the leaf it has reached must announce the sorted order. The whole behaviour of the algorithm, for every input of size n, is frozen into this one tree.
Now the crucial counting move. The leaves are the possible answers, and a correct sorter must be able to output every possible sorted order. With n distinct keys there are n! = n * (n-1) * ... * 2 * 1 different orderings — n! distinct permutations the input could be in. Two different correct answers cannot share a leaf: if two inputs needing different output orders both ended at the same leaf, that leaf could print at most one of them correctly. So the tree must have at least n! leaves, one reachable for each permutation it has to produce.
Here is the bridge from leaves to running time. The number of comparisons the algorithm makes on a given input is the length of that input's root-to-leaf path. The worst case number of comparisons is therefore the longest such path — the height of the tree. So if we can show that any binary tree with n! leaves must be tall, we will have shown that any comparison sorter must, on some input, make that many comparisons. The argument has quietly turned a question about algorithms into a question about the shape of trees.
A short tree cannot hold enough leaves
A binary tree of height h has at most 2^h leaves — the simplest fact about trees, and the engine of the whole proof. The reason is that each level can at most double the number of nodes: the root is 1, level 1 has at most 2, level 2 at most 4, and level h at most 2^h. A leaf can only live at depth at most h, so there are no more than 2^h of them. Short trees are leaf-poor; to hold many leaves you must grow tall.
Combine the two facts. The tree needs at least n! leaves but can hold at most 2^h, so we must have 2^h >= n!. Take logarithms base 2 of both sides: h >= log2(n!). That single inequality already says the height — the worst-case comparison count of any comparison sorter — is at least log2(n!). All that remains is to see that log2(n!) is about n log n, not something smaller.
leaves needed >= n! (one per permutation) leaves possible <= 2^h (binary tree of height h) => 2^h >= n! => h >= log2(n!) = Omega(n log n)
Why is log2(n!) on the order of n log n? A clean estimate avoids any heavy machinery. The top half of the factors in n! — there are n/2 of them, each at least n/2 — give n! >= (n/2)^(n/2). Taking log2, that is at least (n/2) * log2(n/2), which is Theta(n log n). (The famous Stirling approximation pins it down to log2(n!) = n log2 n - n log2 e + O(log n), but we do not need that precision; the crude bound already lands us at Omega(n log n).) So the height is Omega(n log n), and we are done.
The same proof, told as information
There is a second voice for this argument that many people find more memorable: the information-theoretic view. Think of sorting as identifying which one of the n! permutations your input secretly is. Each comparison returns a single yes/no bit, and one bit can at best cut the set of still-possible permutations in half. To shrink a set of size n! down to a single survivor by repeated halving, you need at least log2(n!) halvings — at least log2(n!) bits — which is the same Omega(n log n).
This is not a different theorem; it is the decision-tree argument wearing different clothes. "One bit halves the candidates" is exactly "a branching node has two children"; "log2(n!) bits to single out one permutation" is exactly "height at least log2(n!) to reach n! distinct leaves." Some readers prefer the tree picture because it is concrete and visual; others prefer the information picture because the phrase "a comparison yields one bit, and you need to learn log2(n!) bits" compresses the whole idea into one sentence. Keep both; they reinforce each other.
What the barrier does and does not say
First, the bound counts comparisons, not raw seconds. A method making Omega(n log n) comparisons could still be slow for small n, where constant factors and cache behaviour dominate; merge sort's clean asymptotics do not stop libraries from dropping to insertion sort on tiny subarrays. The barrier describes scaling in a specific cost (comparisons), and as always asymptotics hide constants — it tells you the growth rate that no comparison sorter can beat, not which sorter wins at n = 16.
Second, the barrier is matchable, which is what makes it satisfying rather than merely discouraging. Merge sort makes O(n log n) comparisons in the worst case, so its comparison count is Theta(n log n): the Omega(n log n) floor we just proved and merge sort's O(n log n) ceiling meet exactly. A lower bound and an algorithm that touches it together pin the problem's true difficulty — this is the happiest outcome in all of algorithm analysis, a question fully answered from both sides.
Third, this same leaf-counting template is reusable far beyond sorting. The lower bound for searching a sorted array of n keys — log2(n+1) comparisons — comes from a tree that must distinguish n+1 possible outcomes. The bound is also the seed for harder decision-tree results: element distinctness and convex hull both need Omega(n log n) operations in their richer models, proven by counting how many distinct answers the tree must separate. The technique you just learned is a master key, not a one-off trick.
Where this sits, and what comes next
Step back and notice the shape of what we did, because it is a reusable recipe. The whole proof is a counting argument: count the distinct correct answers a problem can have, observe that a low-branching computation cannot separate too many answers without running long, and conclude a height — that is, a time — lower bound. No specific algorithm was inspected; we reasoned about every algorithm at once by reasoning about the model they all share.
- Fix a model that says exactly what a step is — here, one comparison, with the comparison model's restrictions made explicit.
- Count the distinct correct outputs the problem demands — here, n! permutations, hence at least n! leaves.
- Bound how many outputs a computation of a given length can separate — a height-h binary tree separates at most 2^h.
- Solve for the length: 2^h >= n! forces h >= log2(n!) = Omega(n log n).
Decision trees are powerful, but they have a blind spot: they shine when the answers are many and easy to count, and they struggle when a problem has just one or two possible answers, like "what is the maximum?". For those, the next guide turns to a different and more combative technique — the adversary argument, where an imagined opponent answers your comparisons as cruelly as the rules allow, forcing work out of you no matter how cleverly you ask. After that, the rung closes with lower bounds by reduction: showing a new problem is hard by smuggling a known-hard one inside it.