A First Taste of Algorithms · Order, and Its Price

Dodging the fence

A theorem’s hypotheses, Chapter 5 taught, are where it can be killed. They are also where it can be legally dodged — and this fence has a gate marked clearly in its own wording: sorts by comparing.

Suppose you must sort a million exam scores, each a whole number from 0 to 100. Don’t compare anything. Set out 101 labeled buckets; drop each score in its bucket (one touch per score); read the buckets out in order. Total cost about n + 101 — linear, serenely under the fence. This is counting sort, and it contradicts nothing: it never asks “is a before b?” It exploits something the comparison model deliberately ignores — that these keys are small integers whose values can be used as addresses. Change what you’re allowed to know, and the impossible becomes Tuesday. (The dodge has a price tag of its own: a bucket per possible value. Scores 0–100, fine; arbitrary words or unbounded decimals, no. Problem 3.4 probes exactly where the gate closes.)

The toll-booth question that opened the chapter now closes with real numbers. Sorting costs Θ(n log n) once; each later search costs log n instead of n. One search? Sorting wasted your time. Many searches — and “many” means roughly more than log n of them, a number Problem 2.1 has you make precise — and the toll repays itself forever after. It depends, and now you know exactly on what.

Deeper water: Stirling, and the fence’s exact height

The crude bound n! ≥ (n/2)^(n/2) proved the shape. Stirling’s approximation gives the height: log₂(n!) ≈ n log₂ n − n·log₂ e ≈ n log₂ n − 1.443n. So the fence stands at n log₂ n minus a linear correction — and merge sort’s ≈ n log₂ n sits just above it. The remaining sliver (that 1.443n, and the gap between element-steps and comparisons) is real, and shaving it occupied serious people for decades; merge-insertion sort and its descendants chase the exact minimum comparison count, which is still not known exactly for all n. Even finished questions have unfinished decimals.

Deeper water: stability, and the sort in your pocket

Lab 3’s Break-it 4 made you discover, before it had a name, that merge’s <= versus < decides whether tied items keep their original order. The property is called stability, and it matters the moment items carry more than their key: sort emails by date, then stably by sender, and each sender’s mail stays date-ordered inside — two sorts composing into one organization. (Unstable sorts shred the inner order; Problem 3.5 exhibits the shredding.)

And the sort actually running on your machine? Python’s built-in is Timsort — written for Python in 2002 by Tim Peters, since adopted by Java and others — and it is this chapter folded into one algorithm: merge sort’s frame, insertion sort deployed on small runs (the clocked crossover, productized), an explicit hunt for stretches that arrive already ordered (insertion’s recorded virtue, generalized), stable throughout, Θ(n log n) worst case against the fence. Lab 6’s last experiment times it against your handmade merge sort; the margin you’ll measure is the constants again — the same mathematics, engineered within an inch of its life, plus the small fact that it doesn’t run in Python at all but in C underneath. The shapes are yours now; the constants are an industry.

Where this leaves us

The toll booth’s books are open. Humans sort in n²; the halver sorts in n log n; the gap at scale is the gap between Hollerith’s drowning clerks and a census that finishes. The shapes got their professional names — O, Ω, Θ — as receipts for tables already built. And above everything stands the fence: n log n is not the record, it is the law, proved by counting situations against questions, binding every comparison sort that will ever be written — with a gate, clearly marked, for those willing to know more about their keys than comparisons confess.

One thread was left deliberately loose. The fence is a worst-case fence; insertion sort’s kindness to already-sorted decks hints that other cases have other stories. Chapter 7 walks into the most useful of them: an algorithm that gambles — that lets a coin flip choose its pivot — and is fast not always, not in the worst case, but on average, in a sense that can be made precise, trusted, and measured in your own lab. The strange comfort of the average is the last big idea of the book’s first act, and the doorway to its second.

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