A First Taste of Algorithms · Order, and Its Price

The fence

Now the chapter’s summit. Merge sort pays about n log₂ n. Could something pay less — n, say, or n√(log n), some uninvented cleverness? For algorithms that sort by comparing items (asking “is a before b?” and branching on the answer — every method in this chapter, and nearly every sort ever run), the answer is no, and here is the proof.

Watch any comparison sort run on three items a, b, c, and write down only the questions it asks and the answers it receives. The algorithm’s entire experience of the input is that sequence of yes/no answers — it never sees the items, only the comparisons. So the algorithm is a tree of questions: each internal node a comparison, each branch an answer, and at each leaf the algorithm must stop and announce the sorted order.

Figure 6.3 — The decision tree for sorting three items: six orderings demand six leaves, and a tree of questions with six leaves cannot be shallower than three.

Two facts about this tree, and the theorem falls out:

Fact 1: the tree needs n! leaves. Three items can arrive in 3! = 6 different orderings; n items in n! = n × (n−1) × … × 1 orderings. Two different orderings must reach different leaves — because if they followed identical answer-paths to the same leaf, the algorithm would announce the same rearrangement for both, and the announcement would be wrong for at least one of them (the Diamond makes you nail this, and it is the proof’s load-bearing wall). Distinct situations, distinct leaves: where have you heard this? Chapter 1’s deep water, counting answer-sequences in the guessing game. Same architecture, larger building.

Fact 2: a tree of depth d has at most 2ᵈ leaves. Each question at most doubles the possibilities — count them level by level, the tree’s geometry permits no more.

Therefore 2ᵈ ≥ n!, that is, d ≥ log₂(n!) — some input forces at least log₂(n!) comparisons, whatever the strategy. And log₂(n!) is genuinely of the n log n shape: even without fancy estimates, the first n/2 factors of n! are each at least n/2, so n! ≥ (n/2)^(n/2) and log₂(n!) ≥ (n/2)·log₂(n/2) — the n log n shape with a humble constant, by arithmetic a 7th grader does. (The deep water sharpens the constant with Stirling; for n = 1,024, log₂(n!) ≈ 8,769 against merge sort’s ≈ 10,240 — the fence and the algorithm nearly touching.)

Sit with what was just proved, because it is a different kind of sentence than this book has mostly produced. Not “this algorithm costs n log n” but: no comparison sort, invented or uninvented, run on any machine, ever beats Θ(n log n) in the worst case. The proof never examined an algorithm. It counted distinguishable situations against information per question and fenced in every strategy at once — the move Chapter 1 made on a guessing game, now closing one of the great questions of the subject. Merge sort, the recursion from Chapter 3 you traced with playing cards, is standing essentially against the fence. There was almost nothing left to find, and now you know why.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses