Decision-Tree Lower Bounds

Merge sort, heapsort and their friends all sort n items in \Theta(n \log n) time, and for decades no one could do better with comparisons alone. Was that a failure of imagination, or a genuine wall? This page proves it is a wall. There is a beautiful, model-independent argument that no algorithm that sorts by comparing elements can beat n \log n — so merge sort and heapsort are not just good, they are asymptotically optimal. The proof turns every comparison sort into a tree and then simply counts its leaves.

The comparison model

First, pin down the rules of the game. In the comparison model, the only way an algorithm can learn about the input is to ask "is a_i \le a_j?" and branch on the yes/no answer. It may move elements around freely, but every decision it makes is driven purely by the outcomes of comparisons — it never looks at the actual bit-values of the keys, never does arithmetic on them, never uses them to index an array. Merge sort, quicksort, insertion sort, heapsort: all live inside this model. It is a faithful description of any sort that works on abstract "comparable" objects.

The key observation: on inputs of a fixed size n, the algorithm's entire behaviour is determined by the sequence of yes/no answers it receives. Two inputs that give the same answers to the same questions are indistinguishable to it — it must produce the same output for both. That is the crack we will pry open.

Every comparison sort is a binary decision tree

Trace the algorithm on all inputs of size n at once and you get a decision tree: each internal node is one comparison a_i \le a_j, its two children are the "yes" and "no" continuations, and each leaf is a point where the algorithm stops and outputs a sorted order. Below is the tree for n = 3 — read a root-to-leaf path as one run of the algorithm.

Here is the crucial counting fact. To sort correctly, the algorithm must be able to output every one of the n! possible orderings of the input — for each permutation there is some input demanding exactly that rearrangement, and the tree must have a leaf for it. So the tree needs at least n! leaves (three elements → 3! = 6 leaves, as shown). A comparison never distinguishes fewer permutations than it must, and only a distinct leaf can name a distinct answer.

From leaves to a height bound

The worst-case number of comparisons an algorithm makes is the height of its decision tree — the longest root-to-leaf path. Now marry that with the leaf count using an elementary fact about binary trees:

The last step is to see how big \log_2(n!) really is. By Stirling's approximation n! \approx \sqrt{2\pi n}\,(n/e)^n, so

\log_2(n!) = \sum_{k=1}^{n}\log_2 k = n\log_2 n - n\log_2 e + O(\log n) = \Theta(n \log n).

A quick way to see the lower half of the bound without Stirling: the top n/2 factors of n! are each at least n/2, so n! \ge (n/2)^{n/2} and \log_2(n!) \ge \tfrac{n}{2}\log_2\tfrac{n}{2} = \Omega(n\log n). Either way, the worst-case comparison count is forced up to \Omega(n\log n). The chart shows how faithfully the true \log_2(n!) hugs the curve n\log_2 n.

The verdict: \Omega(n\log n), and it is met

Any comparison-based sorting algorithm makes \Omega(n \log n) comparisons in the worst case.

Because merge sort (and heapsort) achieve O(n\log n) comparisons, the upper and lower bounds coincide: comparison sorting is \Theta(n\log n), and these algorithms are optimal within the model. This is one of the cleanest optimality results in all of algorithms — it does not care which comparison sort you invent next; the n! leaves are waiting for it.

Beating the bound by leaving the model

So how do O(n) sorts like counting sort and radix sort exist? They do not contradict the theorem — they step outside the comparison model. Counting sort never asks "is a_i \le a_j?"; it uses a key directly as an array index, tallying how many times each value in the range 0..k occurs and then reading the counts back out. That indexing is a non-comparison primitive, so the decision-tree argument simply doesn't apply: a single indexing step can split the possibilities into k branches, not just two.

The catch is that these sorts need extra assumptions about the keys — a bounded integer range for counting sort (O(n+k)), fixed-width keys sorted digit by digit for radix sort (O(d\,(n+b))). Buy those assumptions and you escape the n\log n floor; refuse them and, for general comparable data, the floor is absolute.

It is tempting to think n! is "just a product of n things", so its log is a sum of n terms and therefore \Theta(n). But the terms are not constant — they grow. The sum \log_2 1 + \log_2 2 + \cdots + \log_2 n is like the area under \log_2 x from 1 to n, which the integral \int_1^n \log_2 x\,dx = n\log_2 n - n/\ln 2 + \cdots pins at \Theta(n\log n). Half the factors alone (the ones above n/2) already contribute \tfrac{n}{2}\log_2\tfrac{n}{2}, so the sum cannot be merely linear. The \log n per element is real, and it is exactly the number of yes/no bits you need to narrow n! possibilities down to one.

Students often over-remember this theorem as "sorting is \Omega(n\log n)" — full stop. It is not. The bound is scoped to the comparison model. Counting sort and radix sort really do run in O(n) time, and they are not magic and not wrong: they simply don't play the comparison game, so the decision tree with its n! leaves never gets built. Whenever you quote the n\log n lower bound, quote its hypothesis too — "for comparison-based sorting". A lower bound with its model stripped off is a half-truth, and this is the most frequently mangled one in the whole subject.

The dual error is to think radix sort makes comparison sorts obsolete. It doesn't — it needs keys of a known, bounded structure. For sorting arbitrary comparable objects (strings under a custom order, floats by a comparator, records by a key function) you are back in the comparison model and n\log n is the best possible.