A First Taste of Algorithms

Chapter 6: Order, and Its Price

✦ ✦ ✦

In which the toll booth opens its books, and a fence is built around the possible

The bill comes due

Chapter 1 sold you a miracle on credit. Binary search answers in twenty steps what costs a million — provided the list is sorted — and the chapter admitted, in fine print, that sortedness is purchased in advance. Five chapters later, the invoice: what does sorting actually cost? Is the toll worth paying? And — the question that makes this chapter different from every chapter before it — could anyone, ever, sort fast? Not “has anyone” but “could anyone”: is there a floor under the price, built into the universe of the problem itself?

By the end you will hold a proof that there is. It is this book’s first full impossibility theorem, and impossibility theorems are the strangest goods mathematics sells: a fence around every algorithm that exists and every algorithm that ever will, including ones no mind has conceived. Chapter 1’s deep water built a small fence of this kind around the guessing game. Today we build the famous one.

But first, honest accounting of how sorting is actually done.

How humans sort

Pick up a dozen dealt cards the way every card player on Earth does: take them one at a time, and slide each new card leftward through the cards already in your hand until it sits where it belongs. The cards in your hand are always sorted; each arrival walks left past everything bigger than itself.

That is an algorithm — insertion sort — and your hands have known it for years. Its correctness needs one sentence (the hand is sorted before each arrival and sorted after — the invariant trick, which you should greet like a relative by now). The cost, in the declared currency of comparisons: the arriving card is compared against each card it walks past. Worst case — the deck dealt in perfectly reversed order — every card walks past everything already in hand: the first arrival makes 1 comparison, the next 2, then 3, and the bill is

1 + 2 + 3 + … + (n − 1) = n(n − 1)/2

— Gauss’s schoolroom sum from Lab 0, sitting in the middle of sorting, presenting the bill instead of the discount. For n = 2,048 cards: 2,096,128 comparisons. And the gait: double the deck and the bill quadruples — the n² signature you met in Lab 3’s lopsided tree, now arising honestly rather than by sabotage. (One virtue, recorded now and cashed later: deal the cards already sorted and each arrival walks past nothing — n − 1 comparisons total. Insertion sort notices order that is already there. Hold that.)

A human moment

Sorting was an industrial crisis before it was a subject. The United States counts its people every ten years, and the 1880 census — tallied by hand, by clerks, with paper and patience — took about eight years to process. Projections for 1890 ran past 1900: the country would be counting one census when the next arrived. A young engineer who had worked on the 1880 count, Herman Hollerith, proposed heresy: punch each person’s answers as holes in a card, and build machines to sort and tally the cards electrically. His tabulators processed the 1890 census in a fraction of the time, sorting millions of cards by trade, by age, by state — and the company he founded to rent out the machines became, after mergers and a renaming, International Business Machines. IBM. The computer industry is, by lineage, a sorting industry: before machines computed much of anything, they sorted, because sorting was where civilization’s paperwork actually drowned. When this chapter asks what sorting costs, remember that for Hollerith’s clerks the answer was measured in years of a nation’s attention — and that the gap between n² and n log n, at census scale, is the gap between drowning and not.

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