Sorting:
the cost of order

You alphabetise your bookshelf on a Sunday. It takes an hour. Afterwards, finding any book takes about three seconds — you walk to roughly the right letter and you're there. Before, it took maybe twenty seconds of scanning. Beautiful. You've made your life better.

Have you? Run the numbers. You spent 3,600 seconds. You save about 17 seconds per lookup. You'd need to fetch a book 212 times before that Sunday breaks even — and that's ignoring the fact that the shelf drifts out of order the moment you put anything back in the wrong slot.

That is the entire chapter in one image. Sorting is an investment; searching is the payoff. The work is real, immediate, and paid by you. The benefit is small, deferred, and only collected if you actually come back. So the question isn't "what's the best way to sort?" — that one's been answered. The question is does the investment pay?

That's the only question that matters when you're comparing ways of doing work. Not "how many seconds does it take" — seconds depend on your laptop, your mood, and whether the books are heavy. The durable question is about scaling: I hand you twice as much stuff, how much more work is that?

There are only a handful of answers you ever meet in the wild.

• It doesn't care. Twice the pile, same work. Grabbing the top book off a stack takes one motion whether the stack is 10 books or 10,000. Programmers write this O(1) — constant.
• Twice the work. Twice the pile, twice the effort. Checking every book for coffee stains, scanning a list top to bottom. Fair, honest, proportional. That's O(n) — linear.
• Four times the work. Twice the pile, quadruple the effort — because every item has to be measured against every other item. This is the killer. Ten times the books is a hundred times the work. That's O(n²) — quadratic, and it is where good afternoons go to die.
• A little worse than twice. Twice the pile, slightly more than twice the work — and the "slightly" grows so gently you barely feel it. This is the best any general-purpose sort can do, and it is very close to free. O(n log n) — linearithmic.

Now the name: this shorthand is Big-O notation. It deliberately throws away constants and small terms and keeps only the shape of the curve, because when n gets big, the shape is the only thing left standing. A quadratic algorithm with a brilliant implementation still loses to a linearithmic one with a sloppy one — you just have to wait long enough.

Hand someone a shelf of out-of-order books and they'll find the first pair that's wrong, swap it, and carry on. Reach the end, start again. Keep going until a whole pass produces no swaps. Done — guaranteed, because every pass drags the biggest remaining book to its rightful end, like a bubble rising. That's bubble sort, and its main virtue is that you don't have to be taught it.

Its main vice is the bill. Each pass walks the whole shelf, and you need roughly as many passes as there are books. Books × passes = n². A hundred books is on the order of ten thousand comparisons. A thousand books is a million. Double the shelf and you have quadrupled your Sunday.

It gets taught because it's honest about what sorting is — repeated comparison and repeated repair — and because it's three lines long. It never ships, because those three lines are quadratic and there is no amount of clever coding that fixes a curve.

Watch someone tidy a hand of cards and you won't see bubble sort. You'll see this: pick up the cards one at a time, and slide each new one into the right place among the ones you're already holding. The left side of your hand is always sorted; the right side is the pile you haven't got to yet. That's insertion sort, and nobody had to teach you that either.

On paper it's still quadratic — sliding a card into a sorted hand can mean shifting everything, and you do that n times. But it's a much nicer quadratic. Bubble sort re-compares pairs it has already compared, over and over. Insertion sort touches each card once and then only walks as far left as it needs to. Same curve, far better constants.

And it has one genuinely magic property: on nearly-sorted input it's basically linear. If every card is already close to where it belongs, each insertion walks left by a step or two and stops. This is why it survives in production — real sorting libraries (Java's, Python's, V8's) hand small or nearly-ordered chunks to insertion sort on purpose. It's the algorithm that rewards a shelf that's almost tidy, which is the only kind of shelf anyone actually has.

Here's the trick that breaks the quadratic. Instead of sorting the shelf, cut it in half. Sort each half — somehow, don't worry yet — and then merge the two sorted halves by repeatedly taking whichever of the two front books comes first alphabetically. Merging two sorted piles is cheap: one pass, one comparison per book, no backtracking. And the "somehow" resolves itself, because each half is sorted the same way: cut it in half, sort the halves, merge. All the way down to piles of one, which are already sorted for free.

That's mergesort. Count the bill: it takes log₂ n halvings to get down to singletons, and each level of the recursion does one linear pass of merging. Levels × pass = n log n. For a thousand books, bubble sort wants a million comparisons and mergesort wants about ten thousand. That's not a tune-up. That's a different universe.

The idea is older than most of the machines that run it. John von Neumann wrote mergesort down in 1945 — it's one of the first non-trivial programs ever written for a stored-program computer, and it was designed partly to prove that the things were worth building. It has never been beaten on the thing it's good at: it's stable, it's predictable (n log n on every input, no bad days), and it merges from tape, disk or network as happily as from memory.

And it earns its keep in the real world in a way that predates the computer. The 1890 US census had gotten so big that the 1880 count had taken most of a decade to tabulate — the census was in genuine danger of taking longer than the ten years between censuses, which would have been the end of it. Herman Hollerith's punch-card machines did the counting, and the sorting-and-merging of card decks did the ordering. It worked, the census got counted, and Hollerith's company went on to become IBM. Merging decks is still what a database does when your table won't fit in RAM.

Suppose you don't need the shelf perfect. You just need to be able to find things. Then don't sort — bucket. Throw every book into a bin by its first letter: A–C here, D–F there, and so on. Twenty-six passes-worth of thinking becomes one pass, and you've gone from "one enormous search" to "one tiny search" without ordering anything. Inside each bin it's chaos, and inside each bin, chaos is fine — because a bin only holds a few dozen books and scanning a few dozen books is nothing.

This isn't a hack, it's a principle. Exact order is expensive and rarely necessary. Bucketing gets you most of the benefit of sorting for a fraction of the price, because most of what you wanted from "sorted" was just "not having to look at everything." (And if your buckets are even, you can bucket again inside them, and again — which is roughly what a database index is doing on your behalf.)

"Err on the side of messiness."

Searching an unsorted pile is O(n) — you look at everything. That sounds bad until you notice you only pay it when you actually look. Sorting is a cost you pay whether or not you ever come back. A pile charges you per use; a sorted shelf charges you a large fee up front and then a subscription forever, because every new book has to be inserted in its place and every misfiled book quietly corrupts the whole promise.

The Los Angeles Public Library's Preston Sort Center handles millions of items a year, and the sorting there is industrial: conveyors, chutes, staff whose whole job is order. It is absolutely, obviously worth it. Why? Because the maths from the last section flips completely when k is enormous. One sort, millions of searches, by millions of people. The investment is paid once and the dividend is collected by the entire city.

Now look at your inbox. One sort — yours. One searcher — also you. k is small. And, crucially, your inbox has a search bar. Search collapses the cost of finding things in a pile from "look at everything" to "type three words", which means the payoff side of the investment has already been handed to you for free. Sorting your email into folders is paying the sorting cost to buy something you already own.

So: don't file, pile. The rule generalises cleanly. Sort when many people will search many times, and the sort is done once. Don't sort when you're the only user, the searches are rare, or a machine will do the finding for you. Libraries sort. Warehouses sort. Databases sort. You, at your desk, on a Sunday, should mostly not.

Here's where it stops being about books. A comparison doesn't have to be cheap. In a sports league, a "comparison" is a match — ninety minutes, two squads, a stadium. In a flock of chickens, a comparison is a fight, paid for in blood. Once your comparison costs something real, the Big-O of your sorting algorithm stops being a performance question and becomes an ethical one.

Look at a knockout bracket with fresh eyes. Sixty-four teams, sixty-three matches, one champion — and the champion really is (probably) the best, because they beat everyone put in front of them. But ask who's second best and the bracket has nothing to say. The runner-up is just "whoever else made it to the last match", and the genuinely second-best team may have been knocked out in round one by meeting the champion early. A single-elimination bracket is a sorting algorithm that reliably computes exactly one thing: the maximum. It costs a mere n − 1 comparisons, and it buys you exactly one trustworthy number.

Want an actual ranking? Play everyone against everyone — a round robin. That's n(n−1)/2 matches: quadratic, and this is precisely why leagues are exhausting and take a whole season. A 20-team league is 190 fixtures. Double it to 40 teams and it's 780. Nobody has that many Saturdays.

Nature ran into the same bill and found the same answers. A pecking order is a sorting algorithm implemented with beaks: birds fight pairwise until a stable ordering emerges, and thereafter the hierarchy is maintained almost without violence — a glance is enough, because the comparison has already been made and cached. The bloodshed is the sorting cost, paid up front. The peace afterwards is the dividend. Dominance hierarchies look brutal and are, in aggregate, violence-reduction machines: they are sorts that stay sorted so that nobody has to re-run the comparison.

And then there's the human trick, which is genuinely clever: stop comparing everyone to everyone, and instead give each player a number. Elo ratings (chess, and now everything from tennis to matchmaking in your video games) let you infer a full ranking from a sparse set of games, because each result updates a rating and ratings are transitive-ish. Beat someone rated far above you and your number jumps; beat someone far below and it barely moves. You get an approximate global order out of O(n)-ish games instead of O(n²). That's the same move as bucketing: give up exactness, keep almost all the value, pay a tiny fraction of the price.

Mergesort is one of those algorithms that reads better in a functional language than in the language it was invented for. There's no index arithmetic and no buffer — just split, two recursive calls, and a merge that pattern-matches on which head is smaller. Flip between the two panes; they're the same program.

We've just spent a chapter arguing that the pile on your desk is fine. The next chapter goes further and argues the pile is smart — that the reason the thing you need is usually near the top isn't luck, it's an algorithm. Once you accept you can't keep everything in order, the only question left is what to keep close and what to let go of.