Why no comparison sort can beat n log n

Every sorting algorithm that works by comparing two items at a time has a floor under it. Nothing gets below about n log₂ n comparisons in the worst case. The proof is a counting argument that fits on a napkin.

What the claim is

A comparison sort learns about items only by comparing two of them; it never looks at a number's digits or uses its value as an address. MIT's 6.006 calls this the comparison model: items are black boxes, and the cost is the number of comparisons. In this model, sorting n items needs at least log₂(n!) comparisons in the worst case, and log₂(n!) grows like n log₂ n.

Why it matters

Most claims about algorithms are upper bounds: "here is a fast way." Erickson's lecture notes on lower bounds call this bragging about how easy a problem is. A lower bound is the rarer, opposite statement: it holds for every algorithm, including ones nobody has invented. Merge sort and heap sort already reach n log n, so in the comparison model they are optimal.

The napkin argument

Draw every possible run of a comparison sort as a tree: each internal node is one comparison with two branches for its outcomes, each leaf an announced sorted order. A run is a root-to-leaf path; the worst case is the longest one — the tree's height. This is a decision tree, and both sources build the bound on it.

Now count leaves. The answer is a permutation of the n items, and any of the n! permutations could be right for some input. If two shared a leaf, the algorithm would answer both the same and be wrong for one. So the tree needs at least n! leaves.

A binary tree of height h has at most 2^h leaves. So 2^h ≥ n!, and h ≥ log₂(n!). That is the whole proof. Only the number of possible answers fixes the floor, not how smart the algorithm is.

How big is log₂(n!)?

Since n! = 1 × 2 × … × n, its logarithm is log₂ 1 + log₂ 2 + … + log₂ n. The 6.006 notes estimate it by dropping the first half of the terms; each remaining n/2 is at least log₂(n/2), so the sum is at least (n/2) log₂(n/2). Stirling's formula sharpens this to log₂(n!) ≈ n log₂ n − (log₂ e) n, with log₂ e about 1.44. Erickson states the result as: the decision-tree complexity of sorting is Θ(n log n).

The escape hatch

The bound is about a model, and Erickson is blunt that choosing the model is what makes a lower bound meaningful. Bubble, insertion, quick, heap and merge sort all fit the comparison model: they treat two inputs identically whenever every comparison comes out the same way. Radix sort and bucket sort do not. Counting sort takes integer keys from 0 to k−1 and uses each key as an index into an array of k lists — it never asks which of two items is larger. That question has far more than two outcomes, so the decision-tree count does not apply, and counting sort runs in time proportional to n + k. The floor is not broken; it is simply not in the room.

In short

A comparison sort learns one bit per question and must distinguish n! answers. That takes at least log₂(n!) questions, roughly n log₂ n. Merge sort meets the floor within a constant factor. Algorithms that beat it do so by not comparing at all.