08Sort First — Almost Never the Answer, Almost Always the Set-Up

01Four tickets, four teams, one line

Four tickets landed in four different queues on the same Tuesday, and no two of the teams had spoken to each other.

Support had a customer insisting he had been charged twice, and wanted to know whether any two of his fifteen orders were identical. Analytics wanted the same fifteen rows counted into orders per day. Finance wanted them lined up against fifteen rows from the shipping system, to find what one side had and the other did not. Fraud wanted the two orders that arrived closest together in time.

Four teams, four verbs, one table, and not one of the four sentences contains the word sort.

Each team wrote the obvious thing, and the obvious thing was a loop over every pair. Support compared each order against every other order, which is 105 comparisons across that one customer's fifteen rows. The same loop over the day's two hundred thousand orders is about 20 billion of them. Fraud wrote the same loop with a subtraction where support had an equality test. Finance wrote it as a scan of the whole shipping table, once per ledger row. None of them was being lazy. A question about a pair, asked of a pile, genuinely does have to look at every pair, because a pile makes no promise about any two rows in it.

One engineer did something that none of the four tickets had asked for. It went in above all four of those loops, and on its own it answers nothing whatsoever. It does not know which of the four questions was asked. It would have come out identical had none of them been asked at all. A fifth team asking a fifth thing would have got exactly the same work. Nobody had filed a ticket for it because it is not an answer to anything, and the ticket that asks for it is a ticket nobody writes.

What it changed was not the four questions. It changed the table the four questions were being asked of, and every one of the four loops fell apart in the same direction the moment it did. The four teams did not need four fixes between them. The one they needed was not in any of their tickets. No two of them would ever have found it separately, because each of the four was staring at its own verb. What closed all four of them was not the work that answered any of them.

02Split the pile you already own

You already own ten words for this, and you were handed all ten of them one chapter ago. Near, closest, next, between, top, range, prefix, sorted, percentile, within. Chapter 7 gathered those ten into one pile and gave the pile a single exact reason. Every one of them asks where a thing sits relative to the others, and that is a question no key can answer. The reason was true then and it is true now, and it settled the question chapter 7 was asking. This page is asking a different one, so the pile has to be cut again.

Fig. 1 puts the ten words in a tray above two bins. A full ordering answers this, or this only wants a rank. The first bin takes the questions whose answer is a position, held relative to the other items. The second takes the questions whose answer is a rank, which is a far smaller thing to ask for. Nothing is marked as you drop it, no bin is scored while the tray drains, and no counter is running anywhere on the screen. Put all ten somewhere, lock the split, and let the naming do the marking.

Carry chapter 7's pile across whole and six of the ten stay exactly where you put them. Closest, between, next, range, prefix and sorted each name a position, and a line hands you positions for nothing. Two more, near and within, come back flagged rather than scored. Chapter 7 already converted both into equality questions with a manufactured bucket key, so the line answers them and something cheaper answers them too. That leaves the pile short, which is the whole finding. Top and percentile walked out. Both of them are order questions and always were, and a full ordering answers neither of them any better than a bare rank does. So chapter 7's neighbour pile is not one pile, because a full ordering answers only part of it, and those two words are the reason this page exists.

03The tells, in five piles

The split you just locked is one chapter 7 had no reason to draw, so it has to be said out loud rather than left sitting in the tray. Chapter 7 sorted questions into equality and order, and all ten of its order words are still order words. Your first bin, the questions a full ordering answers, and your second, the ones that only ever wanted a rank, cut that order pile straight down the middle. Top and percentile sat beside closest and between on chapter 7's screen, and they are still order questions, but they are no longer line questions. Unless that re-cut is said out loud you are carrying two taxonomies that disagree. One of the two chapters would then have to be wrong.

Here is the first pile, whole. Duplicate, already seen, unique, overlap, gap, consecutive, closest, next, earliest, between two lists, reconcile, merge, smallest equivalent set, the same thing written differently, in order of, and per. Sixteen phrases, and fourteen of them ask about a pair of things rather than about a single thing. Duplicate is a claim about two rows. Gap is a claim about two timestamps. Reconcile is a claim about two files. Two are not pair questions. In order of names an output rather than a test, and per is flagged at the end of this section for a reason. Three of the words you just placed are missing here, and that is deliberate. Range, prefix and sorted are line questions that never walk anything. They ask for an address, and an address is reached by a jump rather than by a neighbour. A later rung hands them to the half of this purchase that is not a walk at all. The pair property is the one the next rung prices.

The second pile is smaller, and the questions in it cost less to answer than the ones above. Top k, the k-th, p99, percentile, busiest, slowest. Busiest and slowest are the same question in a domain's clothes, and both of them name one row out of many. These are order questions and they always were. They simply do not need the whole order. Buying it to serve one of them is an overpayment this page returns to twice.

The third pile is not asking about order at all, and it is the easiest one to misfile because the words sound so close. Is it in there, how many of each small value, must come after, needs, prerequisite. The first of those belongs to chapter 7 and you already know why it does. The third is the interesting one, because it genuinely is about arrangement and still no comparator can be written for it. Nothing in a build graph says that task A is less than task C, and a comparator has to answer that. The tell is needs, and the destination is named eight rungs from now. The second phrase arrives in working clothes as eight million durations, all whole milliseconds under five thousand. Misfile that and you buy an ordering when the value was already an address.

The fourth pile is worth the most money and almost nobody teaches it. Already ordered, comes back in order, each machine's file, stored by key. In every one of those the purchase has already been made, by somebody else, and you inherited it without paying. Ten machines each hand back a file already in key order is that pile at a standup, and misfiling it means buying an ordering you were holding. The fifth pile is the exact opposite of the fourth, and it is the only pile where the reach is to do nothing. What happened first, arrival order, in the order they came in — here the arrangement is itself the answer, and rearranging is not a set-up but a deletion. Show me what happened first has no reach in it whatsoever, and misfiling it costs you the one column nobody ever wrote down.

Two of the words in these piles lie about which pile they belong in, one of them lies twice, and all three lies are worth having. Closest is chapter 7's, and it has been lying to you since you arrived, because it sounds like a question about sameness and no key can make two nearby prices equal. It lies a second time on arrival here, and the second lie is about how many sorts it takes. In one dimension closest belongs on the line, and the nearest value genuinely is the one next door. On a map it belongs on the line too. There the line buys the schedule rather than the adjacency, so one sort answers nothing on its own, and that bill arrives at the rung where this page draws its own limit. The first pile also has a liar of its own, and it is per. It arrives as by, as group, and as for each, which is one word in three costumes. Ordering really does put like beside like, so a grouping job done with a sort looks right and is right. It is also paying for a sequence when a partition was wanted. Grouping is a side effect of ordering and never a reason for it, and that one word will cost you later.

04The pile and the line

That property has a price, and it is the one four teams paid on the same Tuesday without ever seeing the bill. A pile guarantees nothing at all, so any question about a pair has to consider every pair. Fourteen of the sixteen words in the LINE pile ask about two things at once. A duplicate is two rows, a gap is two timestamps, an overlap is two ranges. Two thousand rows sitting in a pile hold 1,999,000 distinct pairs, and page 1 already made you count them. Not one of those 1,999,000 can be ruled out without being looked at, because the pile has promised nothing about any of them. The pile is what makes your loop nested, not the question.

A line guarantees exactly one thing, and it is smaller than it sounds. For any two positions, the item on the left is not greater than the item on the right. That is the entire promise. It says nothing about how much smaller, nothing about what sits between them, and nothing about any key you did not sort on. It is one verdict per pair, delivered for every pair at once, and delivered without your program looking at either item or spending a comparison on it. All 1,999,000 of those pairs are settled the moment the line exists, and you asked about none of them individually. Position implies order, and that sentence is the whole of what you bought.

The ratio you have been writing since page 4 has two halves on this page. On top is what one comparison tells you, and underneath is what the arrangement already guarantees. In a pile that denominator is nothing, so each comparison has to earn its own pair outright. In a line it holds every pair already, so a comparison only has to confirm what position has said. The question did not get easier. You buy the denominator exactly once, before the walk starts, and no question you ask afterwards pays for it a second time. That single guarantee is the denominator, and every rung after this one is spending it.

05Two counters over one table

Here are fifteen order timestamps from one customer, printed in the order they arrived. Beside them sit the four tickets from the top of this page, still filed in four separate queues. Before anything moves, commit to two numbers, because Fig. 2 keeps two counters and they are not the same counter. How many times must this data be rearranged to answer all four of them? And how many times must it be walked? Neither readout prints anything until both of yours are on the board. Yours are pinned, and neither is ever marked wrong.

The number you just wrote down is a price, and the useful question is what you priced it against. A sort feels expensive, because n log n is a longer phrase than one loop. But the loop you were about to write for the first ticket checks every order against every other order, and that loop is quadratic. The gut prices the sort against the question it was asked. It should be priced against the scan it replaces.

The first ticket asks whether the customer double-submitted, which is a claim about a pair. A pile guarantees nothing, so no pair can be ruled out unseen, and the loop runs 15 × 14 ÷ 2 = 105 comparisons before it stops. Then one button. The fifteen slide into order, the two suspect timestamps land side by side, and a single left-to-right walk comparing index i with i+1 finishes in 14 comparisons. The other 91 are drawn greyed, and hovering any one of them prints the reason it never happened.

Read that reason slowly, because it is the whole page. Those 91 comparisons were not skipped by a cleverer loop, and no line in the walk decided to skip them. They were skipped because the arrangement had already settled them, and the walk was handed a licence to never go back. The arrangement did the ruling out, and the walk is only reading it.

Now watch what does not happen next. The sort is not run again. The question changes three times from a dropdown: are any two identical, how many orders per day, reconcile these fifteen against shipping's fifteen rows. Each time the body of the walk changes. Equality replaces subtraction, a run counter replaces a comparison, two fingers replace one. The shape of the walk does not change at all. The SORTS readout at the top never leaves 1, while the WALKS readout beside it climbs 1, 2, 3, 4. Both of your committed numbers are still on screen beside them. Shipping's fifteen rows arrive in date order already, which is rung 3's fourth pile turning up in the wild: somebody else made that purchase and you inherited it without paying. So the SORTS readout is counting yours, and yours is the only one there was.

Priced out in full, the four naive answers cost n(n−1)/2 twice, plus n² for the reconcile, plus n for the per-day pass, which collapses to exactly 2n². At fifteen rows that identity gives 450 comparisons, against one merge sort's 45 plus 72 for the four walks, so 117 in total. 450 ÷ 117 = 3.8, and at fifteen rows that barely argues at all. At fifteen thousand rows the same unchanged move is 450,000,000 against 268,614, which is 1,675 times, and the SORTS readout still reads 1. One of the four deserves an honest note too. The per-day pass costs n whether you sorted or not, so the sort neither helped it nor hurt it.

The closest-pair ticket still owes you a reason, because the walk only ever looked at neighbours. Hover any greyed comparison between a[i] and a[i+2] and the figure gives it in one line. Take two values that are close in time and far apart in the sorted row. Everything printed between them is, by the ordering alone, no further from either end than those two ends are from each other. So a pair like that is never the pair the walk missed, because a tighter one is already sitting inside it. Anything sitting between two close values is closer to both of them, so the smallest gap always lands on neighbours.

06The other cashings, and the axis you did not buy

If the arrangement rules things out, the honest next question is what else it rules out and what it does not. Take the case the walk you just watched cannot handle at all: not one list, but two. Reconciling a bank feed of 200,000 lines against a ledger of 200,000 lines is still a question about pairs, and the pairs now straddle a boundary. Written as the scan almost everybody writes, each line on the left walks the whole right. That is 40,000,000,000 comparisons, and it is the six hours finance complains about every morning. There is no neighbour to look at here. Neither list has an item the other one sits beside, so the adjacency claim has nothing to say.

Sort both lists on (date, amount) and put one finger at the top of each. The order of the two fields inside that key is a decision, not a formality, and it is the only decision here you can get wrong for free. Sort on (amount, date) instead and equal amounts from different days land side by side, which is real adjacency in the wrong thing entirely. The frontier you are about to walk advances on the day, so the day has to be the field that moves slowest. Advance whichever finger points at the smaller value, and record a match whenever the two agree. What makes this legal is not adjacency at all. It is that once you have passed a value on the left, nothing still ahead on the right can ever want it. The two fingers move along a frontier that only goes forward. That is the same licence in a second body: the walk never goes back. A merge sort's worst case on 200,000 rows is 3,337,857 comparisons, and that is the price on each list, taken here and everywhere on this page by the same formula. The merge walk that follows costs at most 399,999 steps, one per row placed but the last. So 40,000,000,000 becomes 7,075,713, a factor of about 5,650. Nothing in the argument depends on there being two lists. Ten machines each hold a sorted four-gigabyte file. Ten fingers merge them into one sorted forty-gigabyte file with exactly ten rows resident in memory. No machine ever needs forty gigabytes of it. Duplicates, gaps, runs, overlaps, nearest values, merges, reconciliations and set differences are this one licence wearing different clothes.

The other cashing does not walk at all. A line gives every item a position, a position is an address, and an address can be jumped to rather than stepped past. That single sentence is what legalises binary search and the index, and here both of them are refusals rather than material. Page 3 already built the sorted row of fifteen values where hunting for 1 touches 8, then 4, then 2, then 1, and costs four. That is where range, prefix and sorted go, the three words the first pile deliberately left out. How many scores fall from 60 to 80 is two jumps and a subtraction of the two positions. Every score below the pass mark is one jump and everything to its left. Neither answer walks anything. Page 9 owns the harder version, where the thing you binary-search is an answer space nobody wrote down. Name the destination, notice that the same purchase paid for it, and keep walking.

Now the limit, which is the expensive half of this rung. A sort buys adjacency in the key you sorted and in no other key at all. Ask for the two closest points among a million on a map. The all-pairs count is 499,999,500,000, so the pull toward a sort is enormous and correct. Sort by x, walk the neighbours, and you will miss pairs that sit thousands of positions apart in x and a millimetre apart on the page. One sort bought one axis. The second axis is not bought by a second sort either, because a second sort undoes the first. It is carried through the recursion as a bound: a strip narrow enough that only a fixed handful of points can live inside it.

So the purchase has two shapes and only one of them is a sort. An order you buy is settled once, holds for the whole run, and answers questions about the key you named. An order in a second key has to be maintained instead, item by item, as things enter and leave while the walk moves. That is upkeep, and upkeep is a running charge a sort does not levy. It belongs four rungs further on and it arrives here early, because the limit cannot be stated honestly without it.

You already ran this, and it needed two orders of which only one was a sort. Page 5's sweep took forty segments and refused to look at all 780 pairs. It held two things at once: a schedule ordered by x and a stack ordered by y. It never merged them, and the page said so on the panel. Name the wrong version too, because it is the one that gets quoted later. Sorting the segments by x and comparing adjacent pairs is not that algorithm and does not work. Two segments can sit far apart in x and cross anyway. The x-sort told that sweep when to look, and the adjacency that found the crossing lived in y and was maintained as it went.

07Your nested loop, and what it costs to buy

Open the last nested loop you wrote. The outer loop walks the rows, and the inner loop hunts through the rest of them for a partner. That double loop is a sort you have not done yet. Chapter 7 said that sentence about a table, and it is worth naming the echo rather than dressing this up as a discovery. The same double loop is two different unbuilt things. Which one it is depends entirely on what the body is asking. Ask whether two rows are the same and the missing structure is a table. Ask where a row sits relative to the others and the missing structure is a line. The loop looks identical either way, which is exactly why nobody sees either one.

The edit is two lines. Sort the collection once, above the loop. Then delete the inner loop and compare each item with the one before it. Everything else in the body survives untouched: the same test, the same accumulator, the same early exit. What leaves is the hunt for the partner, because the arrangement has already put the partner next door. Your next pull request is then one line added and one line removed, and the cost of that function has moved by a factor nobody in the review can name from the diff.

The edit does not occur to you for the reason the click already named: the sort gets priced against the question rather than against the loop you were about to write. Here is that same mispricing on a file worth the argument, and it is a bigger file than the last rung's on purpose. Take the 4,000,000 rows of the nightly export, where the double loop considers every pair and there are 7,999,998,000,000 of those. The same merge-sort formula gives 83,805,697 comparisons on four million rows, and the single walk after it costs 3,999,999. Those 83.8 million comparisons dominate the new total of 87,805,696 completely — and they are the reason that total is roughly 91,000 times smaller than the old one.

So call the sort what it actually is, which is a purchase. Page 3 sold you one of these already and told you to keep it, because an index outlives the run that built it and answers tomorrow's question too. This purchase does not. The order lives in memory for the length of one job, the process exits, and tomorrow's job buys the whole thing again from nothing. A purchase you deliberately throw away sounds like the definition of waste. It is not, and the reason lives in where it gets spread.

The index spreads its price across runs. The sort spreads its price across the passes inside one run. Nothing in the sort knew which of your four tickets you were holding, so every later pass over that array inherits the arrangement for free. The 83,805,697 comparisons are paid once, at the top. The duplicate check adds 3,999,999, and the daily counts add 4,000,000, one per row rather than one per neighbour. The reconciliation is a merge frontier across your file and a partner that arrived in order already, so it adds 7,999,999. The closest pair adds another 3,999,999. Four questions, 19,999,997 steps between them, and the SORTS readout never moves off 1.

The arrangement also buys something that has nothing to do with adjacency, since ordered writes fill each memory page once instead of returning to it twenty times, which is the invoice page 3 warned you was coming. Both halves are paid before the first answer arrives, and that is the honest limit here. A single question with its own one-pass answer never needed the arrangement at all. A duplicate check on those 4,000,000 rows is one hash pass of 4,000,000 probes, set against 83,805,697 comparisons for the order you would then discard. Ask once and it may not pay; ask four times and it always does.

08What the sort deleted

Paid once invites the question this page must not dodge: paid in what, besides time? Time was the price you budgeted for, so it is not the one that hurts. The rest of the bill is easier to read on a program that is already correct than on one that is broken. So here is a correct one.

Twelve CRITICAL lines from last night's outage sit in Fig. 3 in the order they arrived, and they are worth reading top to bottom before anything else on this stage moves. Behind them sit four million lines across five severities (CRITICAL 12, ERROR 1,488, WARN 40,500, INFO 1,204,000, DEBUG 2,754,000), and those five counts sum to 4,000,000 exactly. The on-call is about to order all four million by severity so the twelve criticals come first. That is a legal sort, a correct program, and a green test suite. Commit one verdict before it runs. What does ordering by severity destroy here?

A sort moves rows. Moving a row overwrites where it used to sit, and where it used to sit is sometimes the only place a fact was ever kept. No line of your program declared that fact, so no line of your program will miss it. The severity column survives the sort, and so does every other column on screen. Nothing raises, because the thing at risk was never stored anywhere that could raise. The sort's contract has exactly one clause: is the output ordered by severity? Any shuffle inside a severity group satisfies that clause completely. The twelve criticals alone admit 12! = 479,001,600 orderings, every one of which passes the suite, and exactly one of which is the order the outage happened in. Nothing in the contract obliges the sort to pick that one, and nothing in your tests notices which one it picked. Which of the 479,001,600 you get back is a property of the library build rather than of your data, so it can change the week the library does. The arrangement was carrying a meaning, and the sort has written over it.

One toggle moves that count, and it does not move it a little. A stable sort adds a second clause: equal keys stay in the order they were found. Under both clauses, the number of outputs the contract permits is exactly 1 — the number one, not a smaller enormous number. Inside each severity the arrival order is intact, and the twelve read as a cascade again: the pool empties, the retries pile on, the timeouts storm, the failover fires. Stability is therefore not a footnote about performance. It is the distance between 479,001,600 permitted answers and one.

So the question to ask of any sort you are about to run is what the old positions were carrying. An arrival index costs one integer column, and it turns a meaning the sort would delete into a meaning the sort must move. The arrival order was data, it was never a column, and nothing raises when it goes. Stability is that same property with a name, and the useful thing about a named property is that it composes. You already own why two passes compose, because page 3 made you sort by the important digit first and then watch it fail.

09A comparator is a claim

The last section lost a meaning the arrangement had; this one loses a meaning the comparator never had. You wrote a two-argument function that hands back a negative number, a zero, or a positive one. The algorithm never read it as a function. It read it as a claim, and the claim is enormous: every item you pass in sits somewhere on one line, and this function reports where. Nothing verifies that. Verifying it would cost more comparisons than the sort does, which is exactly why the sort is cheap.

Look at what the trust buys, because you have already watched it being spent. When the walk compared a[i] with a[i+1] and stopped, the pairs it never touched were ruled out by the claim rather than by any work. A sort spends most of its life not comparing things. So the shortcuts are built on the claim, and the claim is the thing nobody checked. Three items, three verdicts, and an is better than instead of a number, so each verdict looks entirely reasonable on its own. Set all three. Then say what the sort hands you back, before you watch it run.

Fig. 4 gives you three items and lets you set each pair by hand. Three items give 3 × 2 / 2 = 3 pairs, and each pair takes one of two verdicts. So three clicks author one comparator out of a family small enough to count, and some members of that family are orders while some plainly are not. Nothing says which is which until you commit. Set the three verdicts, say what the sort hands back, and only then run the merge.

Now the count, and then the mechanism. Each pair has two settings, so three clicks reach 2³ = 8 comparators. Six of the eight are legal, one for each of the 3! = 6 orders of a, b and c. The other two are cycles, so clicking at random authors a broken comparator 2 times in 8, which is 25 percent. The break is mechanical. A merge of two sorted runs does at most len(L) + len(R) − 1 comparisons, and it finishes when either run empties. The standard implementation compares the two run tails first, then drops the empty test on the run that holds the last item, because transitivity guarantees that run cannot empty first. Your cycle makes that guarantee false, and the unguarded index walks off its run. Here run L is one slot and run R is two, so the budget is 2. The left index leaves run L and reads position 2, then 3, then 4. The step counter passes that budget of 2 on step 3 and keeps climbing, and a fourth item lands in the three-slot output on step 4.

Nobody authors that cycle on purpose, so here is the one that arrives by itself. A NaN answers false to all three of <, > and ==, against every value it meets, including itself. Write the ordinary comparator a<b ? −1 : a>b ? 1 : 0 and count the answers: 0 of 3 operators returns true, so the function falls through and returns 0. Zero means equal. It has just asserted that this one value equals every value it is compared against, and those values are plainly not equal to each other. One missing measurement in a column of floats is the entire mechanism.

The third instrument needs no cycle and no NaN. Order three sets by containment: {1}, {1, 2} and {3}. Saying {1} < {1, 2} is honest, and {3} is comparable to neither of them, so the comparator returns 0 twice, once against each. Zero means equal, so it has claimed {1} == {3} and {3} == {1, 2}, and transitivity turns that pair of claims into {1} == {1, 2}. The same function already said {1} < {1, 2}. Three items, one contradiction, and not a single indefensible verdict among them.

Keep this well away from the sort that returns tied items in an order you did not choose. That comparator is legal: it declines to rank equal items, so the algorithm places them wherever the machinery happens to leave them, and it returns every time. A false claim is a different animal, because the algorithm built its shortcuts on top of it. The comparisons the walk skipped were skipped on trust, and that trust can be false. So the useful question was never whether a false comparator returns a wrong order. It is what a program does when the thing it declined to check turns out to be untrue. It does not answer wrongly, it stops answering, inside library code, on somebody else's data.

10Sorted is an invariant, and invariants have upkeep

You now have a legal sort, and tomorrow a row arrives. Everything up to here priced the purchase as something you make once and then spend across four passes, and that price quietly assumed the data had stopped moving. Real data does not stop moving. So the moment you write down that this file stays ordered, you have said something about every future write. You have not said anything about the array in front of you. That is an invariant, and an invariant has upkeep.

The reflex is to keep the promise the way you first bought it, by paying for the whole ordering again. A nightly job appends 400,000 rows to a merged file of 200,000,000 and orders the whole thing from scratch. Those 200,400,000 rows carry about 26.7 comparisons each under the same formula this page has used throughout, so the re-sort costs 5,342,764,545 comparisons every night. Now do it the other way. The batch orders on its own for 7,075,713 comparisons (400,000 rows at 17.7 each). Folding it into the file is then one merge walk, 200,400,000 comparisons, for a night's total of 207,475,713. That is twenty-six times cheaper tonight, and the gap widens every month the file grows. Maintain the order by merging the new rows in, or by distributing them into the buckets that already hold their neighbours, and never by re-sorting.

The version that actually ships is worse, because it does not look like a sort. Somebody puts the sort inside the loop this page just made cheap. A leaderboard rebuilds itself after every score, so 20,000 scores trigger 20,000 orderings of a list that grows one row at a time from 1 to 20,000. Summed over every rebuild, that is 2,523,750,587 comparisons. It is work that 20,000 insertions would have done — and page 1 taught you to price those in both budgets, so here are both: about 266,000 comparisons to find each row's place, and about 100,000,000 element moves to open the hole. The move bill is the larger of the two and it is still twenty-five times smaller than the comparisons alone on the other side, before the twenty thousand re-sorts pay for their own moves. No single call is slow. The profile shows twenty thousand short sorts and not one long one. Nothing on screen looks like the villain, and the flame graph is a lawn rather than a tower. The cost is not in any call. It is in the nesting.

What makes the merge so cheap is that the file was nearly ordered already, and page 1 turned nearly into a quantity — inversions — so you would not have to hand-wave here. A freshly merged file has almost none of them left in it, so the repair after a batch is close to free. Upkeep is cheap in exact proportion to how much of the order survived the last write, which is the whole case for merging.

And that same surviving order, which has just made one algorithm nearly free, is a weapon somewhere else. Page 4 handed a thousand already-ordered numbers to a fixed pivot rule. Quicksort spent 499,500 comparisons where it ordinarily spends 10,986, which is the identical near-order arriving as a catastrophe. So the upkeep question is never only how much order survived. It is also which algorithm you are about to hand it to. The same input, opposite verdicts: nearly free for the insertion sort, ruinous for the fixed pivot.

11When the reach is wrong

Ten rungs have quietly taught a reflex, and a reflex is not a judgement. Three of them did name a price. One axis bought where two were needed, an arrival order written over, a sort nested inside the very loop it was meant to cheapen. But every one of those was a right reach executed badly, and not one of them said the reach itself was wrong. A reader who walks out reaching for a sort on every ordered-sounding sentence has picked up a habit rather than a lever. So this rung runs the tool losing. It loses on two axes, and neither of them is a list of exceptions to memorise. Both are questions about the purchase and not one of them is a question about the sort. A sort that is fast, correct and stable can still be the wrong reach.

The first axis is the one every rung so far has quietly assumed, and Fig. 5 puts it on a dial: how many questions the purchase has to serve. A scan pays nothing up front and then pays in full again on every question you ask it. A sort pays everything up front and charges almost nothing per question afterwards, because the arrangement is still sitting there. So the winner is a threshold, and a threshold is a number you can say out loud. Ten thousand response times, one question asked of them, and the question is give me the ten slowest. Before the dial moves at all, name the number of questions at which buying the order pays for itself.

The second axis is not a cost, and it is the one that catches people. Flip the set from fixed to still arriving and the sort has nothing to arrange. Not because sorting has become impossible. Because what you would keep has stopped being a sorted array. Price that honestly, or the lesson is worthless. Nobody re-sorts ten thousand items on every arrival, so beating that imaginary program proves nothing at all. Keeping the whole order live keeps everything that has ever arrived, and a stream has no last item, so that set has no bound to quote at you. Keeping the ten slowest keeps ten, tonight and next year. The two comparison budgets are close enough to argue about. Ten against a set with no ceiling is not close enough to argue about, and the gap is in the shape of what you hold rather than in the comparison count. Any memory figure you name is a when, never a whether.

Beside that dial sits the list this rung exists to hand over, and each entry carries a destination and a tell. Pure membership goes to a hash table, and chapter 7 built that whole instrument already. Top k from a set that is still arriving goes to a heap, and the tell is the phrase from now on. A single order statistic goes to quickselect. You asked for one of n, not one of n! — page 3 took that logarithm already and handed you the one-sided recursion, and page 19 spends what is left of it.

Small integer keys go to counting them, which you invented yourself on page 3 and do not need shown again. The same question asked repeatedly against growing data goes to an index, because a sort is a purchase you drop when the run ends and this question wants it kept. When the original order is the answer, the refusal is simply not to sort, and the last section showed you exactly what goes missing. A partial order goes to a topological sort, and the tell is needs, or must come after. Two tasks that never depend on each other have no less-than between them at all, so there is no comparator to write. Page 13 spends that one, and it is worth arriving there with the ground still unspent.

One more sits outside those seven, because it does not hand you to another tool at all. Rung 3 flagged per, by and group as the line pile's own false positive and said the word would cost you later. Here is the bill. If nothing downstream walks neighbours, the reach is one partitioning pass that drops each row into the bucket it belongs in, and you were never short of a sequence. Ordering does put like beside like, so the grouping job finishes correctly either way. It just paid n log n for an arrangement nobody afterwards reads.

Notice what none of those seven say. Not one of them says the sort was slow, or badly written, or beaten by a faster sort. Sorting is beaten outright when the purchase serves too few questions to repay itself, or when the set is still arriving and there is nothing yet to arrange. Both of those live in the room, not in the algorithm. That is why the tell is a phrase in somebody's sentence rather than a line in your profiler, and why you can route before you write anything. Seven refusals and one wrong shape, each carrying a destination and a tell, and not one of them is re-derived on this page.

12The seam, and the honest price

Your sort is the right move. Now everything left that can go wrong has nothing to do with the move. The page turns here, and it is worth saying out loud rather than burying in a clause. Everything above this line was recognition, which is the half that fires on sentences containing no algorithm at all. What is left is engineering, and four earlier pages already bought most of it on your behalf. So this is a short section, and that shortness is exactly what honesty about your own reading costs.

Take the receipts first, quickly. Page 1 handed you two budgets and refused to let them collapse into one. Its insertion sort fell from about 250,000 comparisons to about 8,500 when the scan became a binary search. Its move counter did not shift by one. That is why a binary search inside an insertion sort buys you almost nothing, because the shuffling was always the bill. Page 2 derived the cutover and landed on 16, which is why a real library sort stops recursing at sixteen items and finishes the rest by insertion. Page 3's digit dial then showed the asymptotically better sort losing outright once the keys were wide enough. Not one of those is re-derived here.

What no earlier page has priced is memory. A merge cannot write its output over its input, because the two halves it is reading still hold values it has not placed yet. So a merge sort of forty million rows wants a second array of forty million slots. That doubling is what pays for its stability and its dependable n log n. Partitioning does write over the array it read. Quicksort on those same forty million rows carries a stack of roughly 25 frames and nothing else, which is the entire difference between the two families in one line. That trade sits under every library's choice of sort, and it is priced in bytes rather than in comparisons.

The second unpriced fact arrives the moment the array stops fitting. Page 3 told you that one page fetch costs about 100,000 memory touches, and a sort that has spilled to disk is paying near that on comparisons it used to get for free. No cleverer comparison order rescues you here. You sort what fits, write each finished run out, and then walk the runs with the k-finger frontier you already own. One finger per run, and k items resident. Forty gigabytes on a box holding four becomes ten runs and a single merge, and that merge reads each byte exactly once. The two new facts in this section are one fact seen at two sizes. Merging needs a scratch buffer and partitioning does not, and at scale it stops being a sort at all.

13Twenty-five rooms where nobody says the word

Every atom on this page has now been named exactly once, so nothing new arrives here. What arrives is Fig. 6, twenty-five sentences, and eighteen of them never say the word. Read one, and name the lever from nine: sort first, a hash table, a heap, quickselect, count them, an index, a topological sort, one partitioning pass, or do not sort at all. The other seven put a sort on screen that somebody already wrote, and ask what is wrong with it. Both commits lock. The bar counts down from twenty-five and never up, and no running score is shown anywhere.

The tell is the phrase that gave the situation away, and it is on the far side of your verdict. It is not hidden, it is absent — nothing to read ahead, even with the inspector open. That withholding is the whole exercise, because a phrase you were shown is not a phrase you noticed. The seven diagnosis items break the page's own rule and print the word, and they have to. A trap about a misused sort cannot hide the sort. Naming the wrong lever is one skill; naming a right lever executed badly is a harder one, and until now this page has been getting it for free. Nothing scores you. A wrong verdict names the replacement and moves on, because the point is the routing, not the mark.

Twelve of the twenty-five resolved to a sort, six resolved to a different tool, and seven showed you one already written. In five of those seven the answer was still a sort, done differently, so eight items routed away from sorting altogether. The twelve affirmatives did not arrive in two costumes, and no single shape appeared more than three times among them. A neighbour walk, a merge walk, locality, a canonical form, a composite key, and one axis that is not enough.

Guessing gives you three. Eighteen items across nine verdicts is two, seven items across seven diagnoses is one, and three of twenty-five is twelve percent. A reader still carrying chapter 7's reflex, answering a hash table to all twenty-five, scores one. That is what a tool taught only in the affirmative buys you, and it is why the six refusals and the eight routes away are not padding. Recognition exists only after reps, and the reps have to include the ones where the answer is not a sort. Answer sort to all twenty-five and you score twelve, which is precisely the reflex this page was built to beat.

14The payoff

Walking in, you had sorting filed under its output, as a thing you do when you want a sorted list. Walk out with it filed under its effect instead. The effect is an arrangement that licenses a walk which never goes back. That refiling is worth more than any algorithm printed on this page. A filing by output only fires when the word itself appears in the sentence. A filing by effect fires on the sentences that never contain it, which is nearly all of them.

Six things changed hands here, and not one of them is an algorithm. You can read a problem statement you have never seen and name its pile. The words do that work for you — overlap, gap, duplicate, closest, consecutive, and the one of them that misfires. You can look at the double loop in your own file and see a walk you have not earned. You can also say what beats a sort, and exactly where. A hash table for membership, a heap for a set that is still arriving, quickselect for one order statistic. A count for small integer keys, an index when the question repeats all day, a topological sort when the order is only partial. One partitioning pass when you wanted groups and not a sequence, and no sort at all when the original order was the answer. You can choose the key, and the order of the fields inside a composite one, which decides quietly whether the adjacency you bought is the adjacency you needed. You can name the three silent illegalities: an order that was data and was never a column, a comparator that is legal but leaves the answer underdetermined, and a comparator that is a claim and is not true. And you can keep the invariant rather than rebuy it every night.

Two things you already owned changed meaning without any new work. Page 5's sweep stops being a geometry trick. It becomes the case that draws this page's own limit: two orders, and only one of them a sort. That sort bought the schedule, and the adjacency that actually found the crossing lived in the second order and was maintained as the sweep went. Page 3's one-sided recursion stops being a section about medians. It becomes a destination you can route to from a sentence whose only clue is p99. The floor there binds naming one of n! orders, and a percentile only ever asks for one of them.

The course's ratio, cashed for this tool, has two halves you can now read off any problem. What one comparison tells you sits on top. What the arrangement already guarantees sits underneath. A pile guarantees nothing about any pair, so the pile's denominator stays at 1 and every pair has to be asked about separately. A line guarantees position, and that single guarantee is what the four questions on this page were spending. Sorting is the one move on the syllabus whose whole job is to enlarge that denominator, once.

Which is why the price is paid up front and never per question. Everything after the sort runs against the guarantee rather than against the data. So the last thing worth keeping is the shape of the reach, not its name. You are not listening for somebody to ask you to sort. You are listening for a question about pairs being asked in a room where a pile is all anybody has. That is why it is a set-up and not an answer, and why you will now reach for it in rooms where nobody says the word.