03All You're Allowed to Know Is Which One Is Bigger

Page 1 counted five shuffled cards and found 120 orderings. Page 2 put that count aside for a page. Now we pick it up again, and the question is the one page 1 stopped just short of: what does it cost to name which of the 120 you are holding?

Play it as twenty questions. The five cards are face down. You may ask me anything of the form is this one smaller than that one?, and I answer honestly every time. Keep asking and eventually one ordering is left standing.

Most people guess ten, or fifteen.
The answer is seven.

And it is seven in the strong sense, which is the sense this whole page turns on. Seven is not what a clever method manages. Seven is what nobody beats — not you, not me, not any procedure anyone will ever write. There is no code on this page yet and there does not need to be, because the seven falls out of counting alone. That is where a floor comes from.

01One question, and half of them are gone

Ask one question and count what survives. Is card a smaller than card b? I say yes, every ordering that put b first is dead, and 60 are still standing. Now throw that question away and open with a different one. Is c smaller than e? Again 60. That is not luck and it is not a property of the pair you happened to pick. Fix any two positions, and pair every ordering with the ordering that swaps those two values. The pairing touches each of the 120 exactly once, and it flips the answer, so the two sides have to come out equal (120 ÷ 2 = 60). Your opening question is a fair coin whatever you ask. No first question is better than any other, which is a slightly deflating thing to learn about a game you were about to try to play well.

Symmetry only ever covered question one. After it the deck is no longer fresh, and this is exactly where each comparison halves it starts telling you something false. Sixty orderings are left, all of them with a before b. Ask is c smaller than d? and you get 30 and 30, a clean halving, because c and d had nothing to do with a and b and the same swap-pairing runs again inside the 60. Ask is b smaller than c? instead and the split is 20 yes and 40 no. Answer no and you are holding 40 where 30 was on the table. Then push it until it breaks. From the 20 orderings with a before b before c, ask is a smaller than c? The answer is yes for all 20, the no branch comes out empty, and the counter does not move at all. That is a perfectly legal question that buys you literally nothing. Fig. 1 hands you the opening move and takes any prediction you want to commit, then runs these deeper rows in full. And it is that dead branch, rather than any slogan, that makes the number at the end of this section a floor rather than a running time.

So halving is not what a question does. Halving is the best a question can do, and a best case is a thing you can spend. Start at 120 and take the best split every single time: 60, 30, 15, 7.5, 3.75, 1.875, and then 0.94. That is seven questions, and after the seventh there is less than one ordering standing, which means precisely one. Stop at six and you are left with 1.875, which is more than one, so six cannot work for anybody. Now name the thing you just did seven times. One halving is one bit of evidence, and that is the whole of what the word means here. Naming one of 120 costs about seven bits, and one honest yes or no hands you at most one bit, because at best it halves. The count of halvings gets a name as well. We write it lg, so lg 120 is 6.91, and you round it up to seven because there is no way to ask nine tenths of a question.

Five cards is a toy, and the step up to any pile at all is one line of arithmetic you can do yourself. Going from four cards to five multiplies the orderings by five, because the new card drops into any of five places. Multiplying the answers by 5 adds lg 5 questions, which is 2.32. So every card you add costs about the lg of its own position, and the running total is a staircase of bars: 0, then 1, then 1.585, then 2, then 2.32. Add those five and you get 6.91, which is the same seven we counted by hand a moment ago. Ten cards come to 21.8, so about 22 questions, and that one is checkable — 10! is 3,628,800, and 22 halvings takes it under one while 21 leaves 1.73 standing. A million cards cost about 20 questions each (lg 1,000,000 = 19.93), so the staircase looks like 19.9 million from a distance. Its real total is 18.5 million yes-or-no answers, a little lower because the early cards were cheap and the very first bar has no height at all. Fig. 2 draws it one bar per item and will price whatever you think a million costs before it prices the truth. That is the number worth leaving here holding, and not because anyone told it to you. You can rebuild it tomorrow from a staircase you drew yourself.

02The same arithmetic, in a different currency

Now run that same recipe on a smaller question and watch it come unstuck. Forget the full order. I only want to know which of the five cards is the smallest. That is five possible answers instead of 120, so the evidence you need is lg 5 = 2.32 bits. At one bit a question, the floor rounds up to three. Commit to that number before you go any further. Fig. 3 deals you the five cards and exactly three comparisons, and it never once tells you that you are wrong. It prints one readout instead: cards that have never lost. Spend the three the obvious way — 1 against 2, then 3 against 4, then the two winners against each other — and that readout stops at 2. Card 5 was never touched. The bracket winner never lost. Either one could still be the smallest, so you have spent the whole budget and you cannot name an answer. Every other three-comparison plan you try leaves that readout at two or more. The arithmetic was honest and it still was not enough, because a floor is a floor and it was never a promise.

So go and count something else. To be known not to be the smallest, a card has to have lost at least one comparison. Short of that it is still a candidate, and you have no grounds to rule it out. Four of the five cards must therefore end up as known losers. And one comparison produces at most one new loser, since only one of the two cards involved goes down. Four losers wanted, one loser bought per comparison, so four comparisons. Fig. 3's second row redraws those same five cards as a knockout bracket, and the tournament says it straight back to you: five players, four matches, four losers, one champion. Every match makes exactly one loser, and every card but the smallest loses exactly once. Four is also a number you can actually hit, because any bracket at all hits it. So this one is not a floor. It is the exact cost. Keep the ledger the figure leaves you holding: floor 3, truth 4.

Now set the two derivations side by side, because they are one piece of arithmetic done in two currencies. Seven questions for the full order: you needed about 6.91 bits of evidence, and one yes-or-no answer hands you one bit. Four comparisons for the smallest: you needed four known losers, and one comparison hands you one loser. Same shape, twice.

cost = (evidence the answer needs) ÷ (evidence one operation gives you)

That fraction is every speed limit on this page, and it has been hiding in plain sight both times. In both derivations the bottom number is 1. A division by one does not look like a division. It looks like a count, and that is exactly why the interesting half of this fraction has gone unnoticed so far.

So go and move the bottom number. Suppose a question could come back with one of four answers rather than two. Decide now what that does to the seven: nothing at all, half of it, or something you have not guessed. Each four-way answer is worth two halvings, so 120 drops to 30, 7.5, 1.875, 0.47. Four questions where you needed seven, and the only thing that changed was the bottom of a division. Fig. 4 sets both derivations under one pair of labels and then turns that denominator into a dial. Two, three, four or five answers per question give floors of 7, 5, 4 and 3. The halving chain is redrawn each time, so you count the steps rather than trust the division. Both derivations sit under the two labels the fraction was born with: evidence the answer needs on top, evidence one operation gives you underneath. You have now moved that bottom number with your own hand, which makes the next question yours to ask rather than mine. What has been holding it at one bit all this time?

03You proved something about two numbers

Something has to pin that bottom number down, and it is not a fact about the cards. A fraction only binds if you can say what one question is worth. Saying that means writing down what you are not allowed to do. Fig. 5 makes you build the pin yourself, by hand, and it opens by dealing the five cards back out. You get a budget of six questions and one job: sort them. You choose every comparison. The widget expands both answers every time, so what grows on screen is your entire procedure rather than one lucky path through it. A leaf ledger counts as you go. Nothing is revealed and no verdict is offered until the sixth question is spent. Then the ledger stops climbing. Six questions, both branches every time, is at most 2⁶ = 64 leaves — and there are still 120 orderings on the board. Two decks light up sitting in the same leaf: b<a<c<d<e and b<a<c<e<d. Your procedure hands back one answer to two different shuffles, so it is wrong on at least one of them.

You did not fail. Put 120 orderings into 64 leaves and some leaf has to be holding at least two (120 ÷ 64 = 1.875). Read that claim carefully, because it promises less than it appears to. One leaf could be holding 57 orderings while the other 63 hold one each, and the count cannot tell those cases apart. All it gives you is that one collision exists somewhere. One is enough, because a procedure that answers two shuffles identically is broken on one of them. So six questions cannot sort five cards, and that is not a statement about your six. It is true of mine and of everybody's — as long as the only thing anyone is allowed to do is compare two cards and learn which is bigger. Fig. 5 boxes the word only on screen the moment it first uses it, and that box stays up for the rest of the page.

Six questions on one deck is still a small claim, though. Stage two of Fig. 5 turns it into a claim about every procedure there will ever be. Two real sorting methods run on the same five cards, and everything that is not a comparison outcome gets erased: loops, swaps, index arithmetic, all of it. Insertion sort costs at most 10 comparisons on five items (1 + 2 + 3 + 4), so what survives the erasure is a tree at most 10 deep, with room for 1,024 leaves. Merge sort splits five into three and two and costs at most 8 (3 + 1 + 4), a tree 8 deep with room for 256. Two visibly different trees, both with room to spare, and both still have to carry all 120 orderings in their leaves. Neither tree knows it came from a loop. That is what throwing the loops away bought: reach. So Fig. 5 writes the model down and leaves the card on screen: WHAT I AM ALLOWED TO DO · compare two items and learn which is bigger. The entire list being one line long is the point. A bound binds a model, and a model earns its reach from what it discards.

Which means it is worth reading back the sentence you actually proved. Not sorting is hard. This one: seven [ one-bit ] questions to single out one of [ 120 ] answers. Stage three puts a cursor in both brackets and labels them by cause, what I asked for over what I may ask. It prints the fraction rather than only its answer, and every readout is in bits, because bits are the only thing a fraction like this can divide. Three edits, and you make all three.

Top box → which one is smallest. Five answers is 2.32 bits, so it reads 2.32 ÷ 1, floor 3.
Bottom box → a question that can come back with one of five answers. The 120 answers are still 6.91 bits, so it reads 6.91 ÷ 2.32, floor 3 again.
Both at once → 2.32 ÷ 2.32, floor 1.

The truth of 4 from Fig. 3 sits pinned beside that first row, so the floor never gets mistaken for a promise. The second row lands on the same floor as the first with every number underneath it different, which is the whole reason the figure prints the fraction at all. And the third row is worth naming out loud: a question fat enough to answer the whole thing makes the floor meaningless. That degenerate case is the cleanest proof that the two boxes are separate levers, because together they reach somewhere neither reached alone. One honest note that Fig. 5 will not make for you. Nothing on this table returns one of five answers yet. You are being invited to imagine an allowed question, and buying one is a job for later.

Both of those boxes are yours. You wrote the top one when you asked for the full order instead of the smallest card. You wrote the bottom one when you agreed that comparing two cards was the only legal move. Neither number was handed to you by the problem, and neither of them says anything whatsoever about sorting. You have also already pulled a third lever without anyone telling you it was one — back at the tournament, when you stopped counting bits and started counting losers. So there are three: change what you asked for, change what you may ask, or change what you are counting in. Two of them now have an editable box with your cursor sitting in it, and that is not a diagram of a proof. It is the design brief for two entire families of algorithm, and the rest of this page is us going out and buying them. We start at the top box, because asking for less needs no new equipment and nobody's permission.

04Ask for less

So edit the top box, and ask for something worth having. The smallest card is not it. You bought that one for four comparisons at the bracket, with no recursion and no cleverness, and there is nothing left to save. Ask for the middle one instead. Out of a million items, which is the median? That is one of a million possible answers, so the evidence you need is about 20 bits (lg 1,000,000 = 19.93) and the floor is twenty questions. Set twenty against the 18.5 million the full order costs, and the edit has already paid for itself on paper. Now go and collect it. The bracket is no help here at all. Knowing that card 7 lost to card 3 says nothing about where either of them sits in the pile. To call something the median you have to know how many items are below it, and losing a match never reports that. The only method you currently own is to sort the lot and read the middle position. Round the million up to 1,048,576 first, because that is 2²⁰ and it makes the levels come out whole, so the middle is position 524,288. That sort is 20,971,520 comparisons (1,048,576 × 20) to learn one thing. You would put 1,048,575 items in order to find out about one.

What you want is an operation that hands you a rank without counting one. Fig. 6 deals five values into a row, [3, 7, 1, 9, 5], takes the last one as the split value, and parks two markers at the left edge. Before a single step runs it wants your commitment. Once one forward pass over the row has finished, where will the 5 be sitting: position 1, 2, 3, 4 or 5? Every guess is accepted, and then the pass steps one comparison at a time with its claim printed above the markers. Everything at or left of the slow marker is smaller than 5. Four comparisons and two real swaps later the row reads [3, 1, 5, 9, 7], and the 5 is third. The sorted row is printed underneath, [1, 3, 5, 7, 9], where the 5 is third as well. Nothing in that pass went looking for third place. The pass only ever pushed smaller things left, and the marker's final resting place is the count of things smaller than 5. So the readout says 5 is the 3rd smallest, and nobody counted anything to learn it. Click any other value to make it the split and the pass reruns: whatever you choose lands in its finished position and reports its own rank.

A rank is exactly the thing that tells you which side to ignore. You want position 524,288, the pass tells you the split value landed 312,000th, so your item is on the right and the whole left block can be dropped unread. A sort would not drop it, because a sort wants everything ordered and you want one item. So delete one line, one recursive call, and see what goes with it. Fig. 7 builds two trees from identical partition steps on the same 1,048,576 items (2²⁰), and greys out the second call on the right. It asks you first what the deletion saves: nothing, a bit, half, or ten times. Half is the honest guess, and the figure prints it without comment, because you did delete one call out of two. Then both ledgers run level by level. The left tree charges the full 1,048,576 at every one of its 20 levels, a flat rectangle, 20,971,520 in total. The right tree charges 1,048,576, then 524,288, then 262,144, on down, which is page 2's accounting sheet converging to 2n: 2,097,152. Ten times, not two. And the gap widens with n, because it is lg n ÷ 2. A thousand items give 5, a billion give 15. The logarithm was the price of ordering things you were going to throw away.

Both of those totals rest on something the figure says out loud, and I will say it again here: every split landed in the middle. That is a good day, and nobody gets to order good days. Suppose the split value comes back the smallest every single time. Then the side you keep holds n−1 items, and you have spent a whole pass to shave off one. The total runs to about 550 billion comparisons on the same 1,048,576 items (n²/2), against the two million you were promised. So go and buy a split value you can prove is near the middle. Fig. 8 lays 25 values out as five columns of five and sorts each column with the smallest at the top, which puts that column's median in its middle cell. It highlights those five medians, then takes the median of those. Before any shading appears, commit: how many of the 25 are guaranteed to be at least as large as that one? Anything from 5 to 13 is accepted and shaded exactly as you claimed it. Then the honest region is filled in on top of yours. Three columns have a median at least as large as the middle median. Each of those three hands over its own median plus the two cells below it, which are larger still. Three columns, three cells each, nine of the twenty-five.

Read the general rule off the same drawing. Half the column medians are at least as large as the median of medians. Each of those columns contributes three of its five, so at least 3n/10 of the array is guaranteed to sit above it. By symmetry 3n/10 sits below, so the side you keep is at most 7n/10. Both fractions came off the picture rather than off a page. One wrinkle, printed rather than hidden: 3n/10 on 25 items works out to 7.5 while the drawing guaranteed 9, because small cases come out slightly better than the general rule. Now the price of the guarantee. Finding the median of the five medians is itself a selection problem on n/5 items, so it is one extra recursive call, and that call is the entire cost. Groups of five spend 1/5 and keep at most 7/10. 1/5 + 7/10 = 9/10, and 9/10 is under 1. So each level of the ledger is nine tenths of the level above, and the whole thing sums to 10n (1 ÷ 1/10). Drag the group dial to 3 and watch it die: 1/3 + 2/3 = 1 exactly, the sum stops converging, and a shrinking ledger becomes lg n equal levels. Groups of 7 give 6/7 and a total of 7n. The number that mattered was never five, it was the slack under 1. So the top box is bought, and bought twice over. Take the lucky pivot and it costs about 2n comparisons when the splits are kind and n²/2 when they are not. Buy the provable pivot instead and it costs a flat 10n whatever the input does. You paid roughly five times the lucky price to delete the bad day, and the bad day was never something you could see coming. The method has a name, median of medians, now that you own the part of it that does the work. And keep the ledger honest on the way out, because the two ends of this section do not meet. The floor said twenty questions and you have just bought the median for two million. The floor never claimed twenty was reachable. It claimed the full order was never the thing you needed, and that part of it was exactly right. Which leaves the bottom box, still sitting at one bit a question, and that is where the next purchase is.

05Ask for more than a bit

So edit the bottom box. It has read one bit since your very first question, and nothing on this table has ever offered more than that. What would a fatter question even sound like? There is one honest answer, and it is the plainest thing in the world: tell me the value. Not which of two cards is bigger, but the number written on the card. Put a price on that, because this page prices everything. If a key is drawn from a universe of u possible values, then one look at it singles out one of u things. So a single look buys lg u bits rather than one bit. For keys in the range 0 to 255 that is 8 bits a look (lg 256 = 8), eight times what a comparison has ever handed over. Now run the page's own fraction on it. Naming an ordering of a million items costs the 18.5 million bits you counted off the staircase. A million looks at keys drawn from a million possible values buy 19.93 million bits (1,000,000 × lg 1,000,000). That is covered in one pass over the data, with a little left to spare. Look at where the spare runs out. The staircase only ever wanted 18.5 million, so the two sides meet a little below u = n, at about 368,000 possible values. That gap is the same 1.44 bits an item the staircase left lying on the table. So the condition reads u is about n, and the word about is carrying real weight.

There is more in that arithmetic than a bigger number. Taking n looks buys n·lg u bits, and n·lg u is exactly lg(uⁿ), which is the number of bits it takes to write your input down in the first place. So one look per item always buys you the whole input, whatever u happens to be. Evidence was never going to be the thing that stops you here. What stops you is the array of counters you have to build to use it, and that is a bill this section has not opened yet. And when the value is a whole number in a known range, it stops being evidence at all and becomes an address. Picture a hall filling up before a show, where tickets went out in three groups and the usher walks the queue counting heads: twelve in A, nine in B, fifteen in C. Stop right there and notice what did not happen. Nobody held two tickets side by side to see which one came first. Fig. 9 opens on those three counts and nothing else on screen. So the model card takes a second line, written up while you watch: WHAT I AM ALLOWED TO DO · compare two items and learn which is bigger · read a key as a number.

That second line is the whole event of this section, and I want to be blunt about what it did. It did not break the floor you built in Fig. 5. Go back to the word Fig. 5 boxed and left standing on screen: only. The tree in that proof was made by erasing everything that was not a comparison outcome, and reading a key as a number is one of the things that got erased. Seven questions to sort five cards is still true, still true of everybody, and still exactly as unbroken as it was. What changed is which model you are standing in, and you changed it deliberately by writing one more line on a card. The new model comes with a floor of its own, and that floor is easy to find. You have to look at every item at least once, because an item nobody looked at could have been anything. So n operations, and no arrangement of anything ever gets under it. Read it as Ω(n), which is the same promise page 1 taught you to read. That floor is not the expensive part of this purchase, though. The expensive part arrives two figures from now, and it is a bill.

Fig. 9 wants one number out of you before anything moves. Group A has twelve people and group B has nine. Which seat does group B start at? Any answer is accepted, and the seating then runs from it. Type 9 and group B's block draws itself from seat 9, straight over A's last four people, and you watch the collision instead of being told about it. Type 13 and it fits with nothing to spare. Nobody states the rule, because the drawing is the rule: twelve people occupy seats 1 to 12, so the next block has nowhere to begin except 13. Three groups, three starts, 1, 13 and 22. The running total sitting behind those starts is 0, 12, 21, the same three numbers you just reasoned out by hand. A takes seats 1 to 12, B takes 13 to 21, C takes 22 to 36, and 36 is 12 + 9 + 15. Then the figure makes the same move on an array. Eight values, every one of them between 0 and 4: [2, 0, 4, 2, 1, 0, 2, 3]. Five counters collect them, two 0s, one 1, three 2s, one 3, one 4, which totals the eight you started with. Run a total across those counters and you get 0, 2, 3, 6, 7. The figure relabels that row ADDRESSES and walks the input forward. The first item is a 2, so it goes to out[3] and the address for 2 steps on to 4. The next is a 0, so it goes to out[0] and the address for 0 steps on to 1. Eight placements later the output reads [0, 0, 1, 2, 2, 2, 3, 4], and not one pair of items was ever compared.

A step counter runs beside all of that, and it splits the work into three honest parts: 8 steps to count, 5 to run the total, 8 to place, twenty-one in all. Now look at which number is driving which part. Counting costs 8 because there are eight items, and placing costs 8 for exactly the same reason. The running total costs 5 because there are five possible values, and it would still cost 5 if you handed that same range eight million items. Two different sizes, doing two different jobs, and only one of them is the size of your data. The method has a name now that you own the part of it that does the work: counting sort. The running total earns a name of its own, because it turns up a long way from here in buffer layout and in parallel work: prefix sum. And the two sizes get named here as well, because the next figure charges you for confusing them. n is how many items you have. u is how many values could exist.

Fig. 10 pins the item count at 1,000 and hands you a slider on key width, from 4 bits up to 32. It asks for your verdict before you touch it: is a 32-bit key fine, tight, or impossible on a normal machine? Fine is a reasonable answer, and the figure accepts it without comment, because on memory alone it very nearly survives. A 32-bit key means 4,294,967,296 counters (2³²) at four bytes each, so 16.0 GiB (17,179,869,184 bytes). On a 32 GB machine that fits, and the reader who said so was right. So the figure declines to argue about memory. It prints a second readout instead, labelled steps before the first item is placed, and that one reads 8,589,935,592 against a thousand items to sort. Your answer stays on screen beside it. The derivation is printed rather than asserted, because a number that size reads as a boast otherwise. Zeroing the counters is 2³² steps. Running the total across them is 2³² more. The only steps in there that ever look at your data are the thousand sitting between those two passes, so the item count is a rounding error on eight and a half billion. The counter bar is drawn at the same pixels per unit as the data bar, so it leaves the stage and keeps going for 4,294,967 stage-widths while the data bar stays a thumbnail. Now slide back down and the neighbourhood changes fast, because eight-bit keys want only 256 counters against 1,000 items, about a quarter of the data. Sixteen-bit keys want 65,536, already 65.5 times the data. That is the bill for the second line on the card, and it lands in time long before it lands in memory. You cannot afford the universe. You can comfortably afford 256 counters, and that is the whole of the next idea.

06Pay it in instalments

Two hundred and fifty-six counters is an odd thing to be able to afford, so look hard at what it buys. A 32-bit key is four 8-bit digits, and that is the whole of the arithmetic (32 ÷ 8 = 4). A digit eight bits wide has 256 possible values, so a pass that reads one digit wants 256 counters (2⁸) and not one more. Counting sort runs on that unchanged, exactly as Fig. 9 built it. So run it four times, one digit per pass. The universe of keys has not shrunk at all and is still 4,294,967,296 values wide. What shrank is the universe you look at in one go, by 16,777,216 times, and it costs four passes instead of one. That leaves a single thing undecided, and your gut has already decided it. Which digit do you sort by first?

Fig. 11 deals six two-digit keys, [45, 21, 43, 25, 41, 23], and gives you two passes to spend. It takes your commitment before either pass runs: tens digit first, or ones digit first? The tens digit is what most people say, because the tens digit matters more, and the figure runs that choice in full without a word of warning. Pass one on the tens builds two tidy piles and the row reads [21, 25, 23, 45, 43, 41]. Pass two on the ones runs across the whole array the way you wrote it, and out comes [21, 41, 23, 43, 25, 45]. The grouping the first pass built is gone. Nothing is marked wrong, because nothing needs to be. The row is sitting there unsorted and you can read it yourself. Then the figure prints the honest note, because most-significant-first is not broken. It works if each pile becomes its own separate problem, sorted on its own, and never mixed back in until the end. With 8-bit digits that is 256 separate problems after the first pass, each with its own bounds to carry. One label, made where it is made: the figure uses two-digit base-10 keys so the digits are readable on screen, and the mechanism is the one the prose just priced in 8-bit digits.

Run it the other way and the same two passes sort the row. Pass one on the ones digit gives [21, 41, 43, 23, 45, 25]. Pass two on the tens digit gives [21, 23, 25, 41, 43, 45], and that is sorted. Look at where 21, 23 and 25 ended up. All three have a tens digit of 2, so the second pass had no opinion about them whatever, and it left them in the order the ones-digit pass had already put them in. That is the property carrying the whole scheme, and Fig. 11 lets you switch it off. The toggle is not a black box labelled stable or not stable. It is the placement walk from Fig. 9, forward or backward. Flip it to backward and the output reads [25, 23, 21, 45, 43, 41]. Ties came out reversed, the ones-column order the second pass was supposed to be carrying is scrambled, and you are watching it happen rather than being told about it. So the name goes on here. A sort is stable when it leaves equal keys in the order it found them. Instalments compose only when a pass never undoes the last one, and that guarantee lives in the sort you used, not in the loop you wrote. Reading a key digit by digit like this is called radix sort. You are still holding one number I chose for you, and it is 8.

Fig. 12 puts that 8 on a dial running from 4 bits to 24, with the key fixed at 32 bits and a million items to sort. It wants a verdict first: for a million items, is the best digit width 4, 8, 16 or 24? Eight is what nearly everybody says, because eight is what I used, and the figure prices it in full rather than arguing with it. One pass costs the million placements plus a walk over the counters, so an 8-bit pass costs 1,000,256 units. Four passes, 4,001,024 in all (4 × 1,000,256). Then the whole curve is drawn and 16 bits comes in at 2,131,072, a little over half of what your 8 costs. The reason it is not a clean half is the counter array: 131,072 counter-steps at 16 bits against 1,024 at 8. Nobody corrects you. Your 8 stays on screen as a marked point on a curve whose lowest point is somewhere else. The two costs are drawn as separate lines so you can see which one moved. Wider digits mean fewer passes, and 16 is the widest digit that cuts 32 into two equal chunks. A 24-bit digit takes two passes as well, so it does not lose on pass count at all. Wider digits also mean an exponentially bigger counter array, and by 24 bits its 16,777,216 counters have swamped the million items and the total is 35,554,432. Then the item count becomes a second dial, and the lowest point moves under it. A thousand items want 8-bit digits and 5,024 units of work, where 16-bit digits would cost 133,072. A million items with the same 32-bit key want 16. The best digit width is not a property of the key. It is a property of the key and how much data you have. One last reading off that screen, and it is the uncomfortable one. At a million items radix does about 2.13 million units of work against the 19.93 million comparisons a comparison sort needs (n lg n), nine times fewer. The comparison sort can still win. Big-O is not a decision procedure, and the reason this one can lose is something the page has not priced yet: where the data physically sits. I am not putting a number on that here. The last idea on this page is where that number gets earned.

There is one more instalment plan, and it starts by killing a misreading. The trouble was never that you do not know the range. A range can be perfectly well known and completely useless. House prices from 0 to 2,000,000 want 2,000,001 counters, which for five thousand houses is 400 counters per house. Any float between 0 and 1 fails differently and worse, because between any two of them there are more of them, so a counter per value is not something you can even define. What you might know instead is how the values are spread, and a spread is enough to compute an address. Carve the mass into n slices holding about one item each, drop each item into its slice, then tidy each slice with an ordinary comparison sort, which is free at size one and quadratic at size n. Fig. 13 spreads a hundred values over a hundred slices with a skew slider sitting at zero. Commit before you touch it: if the data all crowds into one slice, does the cost stay put, get a bit worse, or change shape? Every answer is accepted, and then you drag. The slices empty one by one, the items funnel into the last one standing, and the readout climbs from 100 to 10,000. A hundredfold, and it is a hundredfold because the comparison sort inside that one slice is quadratic. Then the readout is relabelled as what it always was: the sum of the squared slice sizes. A hundred slices of one gives 100. Ten slices of ten gives 1,000 (10 × 10²). One slice of a hundred gives 10,000 (100²). The condition was never that your data is uniform. It is that the squares stay linear. That is bucket sort, and the model card takes a third line while you watch: know how the values are spread. Still the same purchase, a fatter question bought on a weaker assumption each time. Now notice what every address on this page has had in common. It had to put the item in the seat it will hold in the finished order, and that is the last assumption left to drop.

07Stop asking for an order

So drop order-preservation — not because the address function is easier without it, though it is. Drop it because the thing that assumption was buying is a thing I have stopped wanting. I do not want a finished sequence at all. I want to put an item down and find that one item again later, and nothing else. Name the loss first, because it is real and it never comes back. The output is not in order, and no amount of care will make it so. Ask this structure for its smallest key and it has nothing to say. What you get in exchange is that the address function stops having to respect anything. It no longer has to send smaller keys to smaller addresses, because there are no smaller addresses. It can be computed from an integer, a string, a whole record. That freedom is not a bonus. It is the exact thing order-preservation had been charging you for, and you only see the price once you refuse to pay it.

So write the freest address function there is. Ten slots, numbered 0 to 9, and a key that is a whole number. Send key k to slot k mod 10, the remainder after dividing by ten. Key 37 goes to slot 7, and key 82 goes to slot 2. No range to know, no spread to assume, and not one comparison anywhere: one division and you are holding an address. The function is a hash function and the array it addresses is a hash table, and neither word does any work the arithmetic has not already done. Now insert 47 — 47 mod 10 is 7, and slot 7 is already holding 37. Two keys, one slot, and the whole idea in trouble on its second insertion. The word for that is collision, and the useful question is whose fault it was.

Not your data's — yours, and it was settled the moment you chose the function. Say your keys can be any number from 0 to 999. That is 1,000 possible keys arriving at 10 slots, so some slot is the destination of at least 100 of them (1,000 ÷ 10). The arithmetic is the whole argument, so run it backwards. If every one of the ten slots owned 99 keys or fewer, the ten together would own at most 990 (10 × 99), and ten keys would have nowhere to go. Now notice what that sentence never mentioned. It never mentioned your data. Fig. 14 hands you four functions and a box to type your own, and it makes you commit before you choose: does anything on that list dodge collisions completely? Then it runs whatever you picked across all 1,000 possible keys and draws the ten columns. The MAX POSSIBLE KEYS PER SLOT readout will not fall below 100 for anything you can write. Nobody there tells you to stop hunting. You watch the counter refuse to move. So the design question was never how to avoid a collision. An input that collides always exists, so the real question is what you do when one arrives.

Forced is not the same as fair, though, and the second row of Fig. 14 is the separation worth the whole figure. Try 5k mod 10, which obeys the pigeonhole exactly as the others do. It also puts 500 possible keys in slot 0 and 500 in slot 5 and none at all in the other eight (5k is 0 or 5, never else). Same forced minimum, an entirely different disaster. Collisions are forced. Clustering is your function's own doing. And "some slot owns 100 possible keys" is still not "a hundred items collide", which is why the figure's second panel stops reasoning about the universe and inserts five real keys instead. With an even function those five land clean, no collision at all, 30.2% of the time (10×9×8×7×6 ÷ 10⁵). Print that number rather than reassure with it, because 30% is a minority. So handle the collision instead of hoping about it. The plain way is to hang the keys that share a slot off it in a list, a chain, and to walk that list when you arrive. Then the one dial you have is items over slots, n/m, and it is not a ratio to admire. It is the average chain length, literally. Five keys in ten slots reads 0.5, and thirty keys in ten slots reads 3.0. Its name is α, and the name is worth far less than the number standing beside it.

Now count what those chains cost. A chain is pointers, and every pointer is memory that could have been another slot. Lower α is the only thing that helps you, and slots are the only thing that buys it. So spend the pointer money on slots and drop the chains: when the slot you want is taken, walk forward and take the next free one. Fig. 15 does that with h(k) = k mod 10 and three keys chosen so their walks cross. 37 hashes to slot 7, which is free, and lands in one probe. 47 hashes to slot 7, finds 37 there, steps on to slot 8, two probes. 57 hashes to slot 7, meets 37 and then 47, and settles into slot 9 on its third. To find a key again you replay that same walk: start at h(k), step forward, and stop when you either see your key or hit an empty slot. Searching for 57 costs three probes and gets there. That rule is the entire search, and it is about to break in a way that teaches more than it works.

So delete 47, which means blanking slot 8, because that is what deleting obviously means. Before searching again, commit to an answer: which key, if any, can you no longer find? Nearly everyone says 47, and Fig. 15 tests that one first, and it holds up: searching for 47 reports not found, exactly as intended. Now search for 57. Slot 7 holds 37, not it. Slot 8 is empty, so the walk stops and reports not found, on a key sitting in slot 9 and highlighted on your screen. The key that broke is not the key you deleted. And the walk was right to stop, which is the part worth keeping. If 57 were in this table at all, slot 8 is where it would have been put. The emptiness was never missing information. It was the proof. Run that probe walk through the page's own fraction and you can price what you demolished. The answer "somebody else's key" settles exactly one slot and sends you one step further along. The answer "empty" settles the entire rest of the walk in a single look. Those two answers are not worth anything like the same, and a table's whole search cost rests on the fat one. The repair is a marker reading was occupied: search reads it and keeps walking, so 57 comes back in three probes again, and insertion ignores it and reuses the slot, so no space is lost. Do not remember the marker. Remember what it protects: when a search stops, ask what the absence is claiming.

08Buy it once and keep it

That marker was the last thing on this page bought inside a single run, and so was everything before it. The theatre's counts, the prefix sums, the bucket boundaries, the probe walk: each one was built at the start of a job, used once, and dropped on the floor when the job ended. Now look at what the habit costs you. The expensive part of most of those purchases never depended on the question you were asking. It depended only on the data sitting there. So ask the obvious thing. What if you kept it? An index is that question answered yes. It is the same denominator purchase you have been making all page, and the only difference is where the price lands. Buy a fat question inside one run and one run has to pay for it. Buy it once and keep it, and the price spreads over every question you will ever ask. That is why you can afford something here that would be ridiculous inside a single job.

So what is the cheapest thing worth keeping? Hold the data in order, and stop there. No pointers, no nodes, just a row you sorted once and did not throw away. One look pays properly now, because comparing your target against the value in the middle throws away half the row whichever way the answer comes back. Price that on the page's own fraction, because none of it is new. Fifteen values means fifteen possible answers, so naming one costs lg 15 = 3.91 bits. One comparison against one value buys you one bit, so 3.91 over 1 rounds up to four looks, and that is the entire derivation. Fig. 16 lays the fifteen values out in a row and takes your worst case before it lets you step anything: over all fifteen possible targets, what is the most looks any single one of them can cost? Whatever you commit is accepted, and then the figure runs all fifteen searches in front of you and prints the longest. Hunting for 8 is finished in one look. Hunting for 1 touches 8, then 4, then 2, then 1, and costs four. Four is the maximum over all fifteen targets, four is what the division said, and it is the same fraction as the five cards on a smaller numerator.

The second row is where the figure stops being about searching. Every position ever used as a midpoint lights up and stays lit, and after fifteen searches the whole row is on. Look at the order it lit up in. 8 came first, alone. Then 4 and 12. Then 2, 6, 10 and 14. Then the eight odd numbers. Four ranks of 1, 2, 4 and 8, which totals exactly the fifteen positions you began with. Nobody drew that shape: the searches drew it, and they drew the same one every time, which is what the third row is counting. Each search works out its own midpoints, and the ranks tell you how many: one for the search that lands straight on 8, two each for the pair at 4 and 12, three each for the four below them, four each for the eight along the bottom. That comes to forty-nine computations between them (1 + 4 + 12 + 32). Those forty-nine produce fifteen distinct numbers, which means thirty-four of the forty-nine re-derive a number another search already had. Store the fifteen once and all of that recomputation is over. Take the names while the picture is still in front of you. The value on top is the root, the values hanging under a value are its children, the four ranks are levels, the eight along the bottom are leaves, and walking from the top down is a descent. And the moment that shape is stored, arithmetic stops choosing it for you. The rule (lo+hi)/2 picked those midpoints while they were being recomputed. Now you pick.

So pick the shape out of the key itself, the way you picked the passes in radix sort. Fig. 17 hands you 20-bit keys and reads five bits per level, which is 32 possible chunks and therefore 32 children at every node. Twenty bits covers 1,048,576 possible keys (2²⁰), so the table has room to grow. Type a key and step down, one chunk at a time. Before you type, commit to one thing: the table grows from ten items to a hundred thousand, and the depth does what? Every answer is accepted, and then the growth runs. Items climb 10, then 1,000, then 100,000, while the DEPTH readout sits on 4 and never twitches. The reason is printed right beside it: each level ate five bits of the key, and the key did not get longer when the data did. A balanced search tree over the same 100,000 items is drawn alongside at 17 levels (lg 100,000 = 16.61). The chunk dial is Fig. 12's knob wearing different clothes. One bit per level gives 20 levels and 2 children. Five bits gives 4 levels and 32 children. Ten bits gives 2 levels and 1,024 children. Fewer steps against a wider node, met once in sorting and now again in lookup. And the comparison counter reads zero at every setting, because no level here compares anything. You are back to the key being the address, one instalment per level, and the structure has a name: a trie. One label where it is made: the figure draws the dense case, a node per used prefix, and a real trie on scattered keys pays for the empty children it allocates. That space cost is the same bill the counter array sent you.

Each node in that trie holds children and nothing else, which is a waste of a good node. So what is the smallest useful fact you could cache inside one? Answer before you read on, and keep the answer small, because small is the point. One bit will do it: is there anything in this region at all? A node covers every key below it, so that single bit speaks for the whole subtree underneath. Arrive at the node, read the bit, and if it says empty you skip the entire region without descending into it at all. "Recurse to find out" has become "look and decide", and it cost one bit per node. That is the cheapest claim on this page worth storing, and the next move cannot be made without it.

Now stop chunking the key from the left and cut it in half instead. A 32-bit key splits into a top 16 bits and a bottom 16 bits, and the top half says which block you are in. One look at that block's summary bit then says whether the block is empty. Either answer leaves you holding a 16-bit problem, and the same move applies to that. Fig. 18 stands two counters side by side, ITEMS REMAINING and BITS OF KEY REMAINING, and makes you name which of the two halves before the step button will do anything. Items remaining is what nearly everybody picks, and it is a fair guess, because every halving on this page so far has halved items. The figure accepts it, wires it to the button, and lets you step. The bit counter goes 32, 16, 8, 4, 2, 1 — five steps, and the key is gone (lg 32 = 5). The item counter sits on a million and does not move once, with your prediction still on screen beside it. Five levels, for any number of items at all.

Before that settles too comfortably, look at what bought it. u again, the whole universe of possible keys, sitting in memory. One summary bit for every key a 32-bit field can hold is 2³² bits, or about 537 MB, and the figure says plainly what that number is. It is an order-of-magnitude claim about one bit per possible key, not the measured footprint of any named structure. Now set it against the counter array. That wanted 2³² counters of four bytes each, 16.0 GiB, so one bit per key comes in 32 times cheaper. The same universe, spent in a different direction. The bill did not go away, and it never does. You looked at it and decided you could afford it, which is a different sentence and an honest one. One last reading before those counters leave the screen. This figure halved the key. The next one halves the data, and a billion items halved takes 30 steps (lg 10⁹ = 29.9). Five against thirty, the same fraction both times, and all that changed is which quantity you put on top.

09You are not billed in comparisons

Every count on this page has treated operations as if they cost the same. They do not, and the gap is not small. Fig. 19 pins a billion keys on the table and hands you one dial, the fanout of a node, running from 2 up to 1,000. Two meters run beside it. One counts COMPARISONS PER LOOKUP, and the other counts FETCHES PER LOOKUP, where a fetch is one read of a page off the disk. A page is the smallest lump the hardware will hand you, a few thousand bytes, whether you wanted one key out of it or a thousand. Before the dial will move, the figure makes you commit to which meter you are trying to make small. Comparisons is what nearly everybody picks, and it is a fair answer. Comparisons are the only currency this page has used for thirty steps. So the figure takes your answer and optimises it honestly. It drives the dial to the setting with the fewest comparisons, which is fanout 2, and both meters read 30 there. Then it prices the currency on screen. In the time one page fetch takes, a machine can touch memory on the order of a hundred thousand times. Your optimum was optimal in the currency nobody bills you in.

Now widen the node and watch both meters run at once. Naming one key out of a billion needs about 30 bits (lg 10⁹ = 29.9), and that number never moves. What moves is the bottom of the fraction. One comparison buys one bit, so 30 over 1 is 30 comparisons. One fetch of a node with f children buys lg f bits, because reading that node tells you which of its f branches your key lives in. Levels are therefore 30 divided by lg f, and you can check every setting by multiplication instead. Ten children per node: nine tens multiplied together (10⁹) is a billion, so nine levels. A hundred children clears it in five, since 100⁵ is ten billion and 100⁴ is only a hundred million. A thousand children, and do this one yourself: 1,000 × 1,000 × 1,000 is a billion exactly, so three levels. Keep the root resident in memory, since there is only ever one of it, and the lookup costs two fetches. Meanwhile the other meter climbs. A node with f children holds f−1 keys, and scanning them end to end costs all of them, so comparisons go 30, 81, 495, 2,997. A hundredfold rise, on the meter you said you wanted small.

So price the whole thing, in the currency that bills you. The fair comparison is not against comparisons in memory. It is against the same billion keys in a two-child tree that also lives on disk, 30 fetches deep. At a hundred thousand memory touches per fetch, that lookup costs 3,000,000 touches of equivalent work. The fat-node tree costs three fetches, which is 300,000, plus the 2,997 comparisons it does inside those three nodes. The bill comes to 302,997, which is 9.9 times cheaper, or 14.8 times with the root resident (202,997). Now look at where the 2,997 sits inside that total. It is one percent of the bill. There is the sentence with a number under it at last: you are not billed in comparisons. You bought a hundredfold more of them and the total moved by one part in a hundred, because the thing you do pay for fell tenfold. Every database index on earth is fat for that reason and no other.

Two honest notes before this leaves the screen. The comparison meter only climbs if the node is scanned from one end to the other. Run a binary search inside the node instead and the count stays near 30 at every fanout, at no extra cost, because the node is already in memory once you have fetched it. Fig. 19 states which method its meter uses, and it uses the linear scan, so the climb you watched is the worse of the two. Second, on flash the ratio is far smaller than a hundred thousand. The fetch is still the thing you are billed for, so the shape of the answer holds; only the size of the win shrinks. And now the digit dial closes. Radix sort lost there to a sort with worse asymptotics, and this is what beat it. Each pass scattered items to hundreds of distant addresses, and every scatter dragged in a fresh lump of memory to place one single item. Counting operations as equal was always the fiction. The model card takes its last line — fetch a page — and this one arrives with a price printed beside it.

That is the page, so take it. Fig. 20 reopens the model card with three boxes and four questions this page never solved. How many answers could there be. What does one allowed operation tell me. What am I counting in. You fill all three and commit a floor, and only then does any answer appear. Look up one word in a 170,000-word dictionary: that is 18 bits (lg 170,000 = 17.4), which is 18 comparisons if comparisons bill you and 2 fetches if page reads do. Same numerator, two right answers, and you picked which. Sort a billion 64-bit keys: you need 2.99×10¹⁰ bits and one key read buys 64 of them, so 0.47 reads per item would cover it. But u is 2⁶⁴, so you buy it in four instalments of 16 bits, and you have just re-derived radix. Then the one that hurts. Find the top ten scores out of a billion: your floor is 299 comparisons and the true cost is a billion, because you have to look at every item. Nobody corrects you. You watch your own correctly-computed floor sit three million times under the truth, which is the five cards arriving again under your own hand. A floor tells you where to start looking, never where you land. The closest pair in a list of 1,000 says it once more, quietly: floor 19, truth about 10,000. A fourth control then asks which lever you would buy, and it reports what you specified rather than what it is called. Shrink the numerator and it describes one-sided recursion. Fatten the denominator to a key read and it describes counting in instalments. Change the currency to fetches and it describes a fat node. The names print last and greyed, because the specification is the part that is yours.