The head each piece will meet

The rotation that could be priced gave a sort a way to decide, before moving anything, how to finish a file that arrives almost sorted. The file is 65,536 keys, sorted except for a last tenth appended in random order from the top fifth of the keys, a run whose shape the input itself declares. Sorting that tail a buffer’s worth at a time leaves sorted pieces, and the sort can send each piece straight into the head or merge the pieces to one group first and cross the head once. The rule priced both ends from measurements of the library merge on synthetic runs: a table of what one sorted run costs to cross a head it interleaves with, by the run’s length, the buffer and the head keys above the run’s smallest, and the measured cost of merging random pieces to one group. The long crossing came within 3% at every buffer, and the rule chose the cheaper end at six of seven buffers and nine of ten reaches of the tail.

Where it failed, it failed the same way. It priced every piece against the head as it stood before any piece joined it, and every piece after the first also crosses the pieces merged before it, so the pieces’ price fell further behind their cost the more pieces there were: 89% of the cost at a 16th, 67% at a 1,024th. At a 256th that sent the sort to the dearer end, and so it did at a 1,024th with a tail drawn from the top tenth of the keys, where the original head has no keys above any piece at all.

Its closing section proposed counting what each piece will really cross. The pieces are sorted before any of them is merged, so the number of keys in an earlier piece above a later piece’s smallest is one binary search of the earlier piece. A piece’s true count is the original head’s keys above its smallest plus the sum of those searches over every piece merged before it. The prediction was that, priced at that count, the pieces would come within 5% of their cost at every buffer, and the rule would choose the cheaper end at all seven buffers and all ten reach settings. It named two risks: the searches, eighty thousand of them at a 4,096th, and the table, which prices one run’s crossing and might not price the many short crossings a sequence of pieces makes.

The prediction holds, nearly to the number, and the more interesting result is how regular the thing it repairs turns out to be.

The head a piece will meet #

The file, the buffers, the two ends and the price tables are the earlier essay’s, and every move is the library merge’s own count. The rule changes in one place. For the $i$-th piece in the order the pieces go into the head, it reads by binary search how many of the original head’s keys lie above the piece’s smallest, as before, and then, for each of the $i - 1$ pieces before it, how many of that piece’s keys lie above the same smallest; the sum is the piece’s crossing count, and the crossing table prices the piece at it. Merging first is priced exactly as before. The rule takes the cheaper end, and the end it chose is compared with the ends’ measured costs.

The table is still read for a head the length of the whole file, although the head a piece meets grows by a buffer with every piece merged. That is a simplification of the earlier essay’s that this one keeps.

Within six per cent at every buffer #

Priced against the head each piece will meet, the pieces’ crossings come to between 94% and 104% of what they cost at every buffer, where the head as it stood priced them at 63% to 89%. The error that grew with the number of pieces is gone. At a 256th the price is 4% high, at a 1,024th it is within half a per cent, and only at a 4,096th, with 410 pieces of sixteen keys each, is it 6% low. The prediction’s 5% holds at six buffers of seven and misses by one point at the last.

What changed is only the count. The crossing table was right about what a crossing costs given how many head keys it passes; the earlier rule had asked it the wrong question, a count taken before the head changed. With the right count the same table, measured on single runs crossing a static head, prices a sequence of a hundred or four hundred merges into a head that each one enlarges, to within a few per cent. The second risk the closing section named, that many short crossings might not behave like the single crossing the table measured, does not appear until the pieces are sixteen keys long, and then as a 6% shortfall.

Exact, without the table #

The table is not needed for the pieces at all, and the reason is in what a piece is. A piece is a buffer’s worth of keys, so it always fits the buffer, and a merge whose shorter side fits the buffer does not rotate, which is the guarantee the library makes only when its allocation succeeds: the library merge copies the piece into the buffer, then walks the head from the piece’s smallest key upward, moving each head key it passes once and each piece key back once. Its cost is the head keys above the piece’s smallest plus twice the piece. The earlier rule’s shift price had two mistakes in it, the count of head keys, which ignored the pieces before, and the piece’s keys, counted once instead of twice.

With both mended, the shift price of the pieces sent straight in is the moves the sort makes, exactly, at every buffer: 30,306 moves at a 16th, 137,923 at a 128th, 1,008,296 at a 1,024th, 3,806,847 at a 4,096th, priced and paid. The one exception the counting must allow is a key of a piece that lies above everything merged before it, which the merge’s trim leaves where it is; on this file that happens to no key at any buffer, and on a file of 16,384 keys of the same shape it happens to one, and the count that leaves such keys out is exact there too. The crossing table, measured on single runs, gets within 4% of these at six buffers and 6% at the seventh, so its errors were the table’s own interpolation, not a property of merging pieces in sequence. The second risk the closing section named, that many short crossings might not behave like one long one, is answered more sharply than it asked: a short crossing is a sequence of shifts, and shifts are counted exactly.

The rotation, then, is the only part of either end that needs measuring; everything else is moves that can be counted in advance, as the least any sort must move can be. The long crossing of the tail merged first does not fit the buffer and rotates, and only a measured table prices it; the rounds before it rotate too, wherever a group outgrows the buffer. Everything that fits the buffer can be priced by counting, and the counting is what the earlier rule got wrong.

The cheaper end, every time #

With every piece priced against the head it will meet, the rule chooses the cheaper end at all seven buffers. At a 256th, where the earlier rule sent the pieces in at 5.00 moves a key, it now prices sending them in at 5.16, above the 4.38 it prices merging first at, and merges them first, which costs 4.35. At every other buffer it makes the choice the earlier rule made, now for the right reason: at a 128th, where the two ends differ by a third of a move a key, the pieces are priced at 3.27 against their cost of 3.20 and merging first at 3.60 against 3.55.

The two price curves now lie along the two cost curves at the scale of the plate, and cross where the cost curves cross, between a 128th and a 256th. That crossing is what the earlier essay’s question was about, the boundary between the ends, and it can now be found from prices alone. A sort that knows its buffer and can binary-search its pieces knows, before it moves a key of the tail, which way to finish.

A third of every crossing is other pieces #

At every buffer from a 32nd down, 32% to 33% of the keys the pieces cross belong to pieces merged before them; at a 16th, with two pieces, 24%. The share is nearly constant because it is arithmetic. The tail is drawn from the top fifth of the keys, 13,107 of them, and takes half, so the head holds the other half of the band, about 6,553 keys, as many as the tail. A piece whose smallest key lies near the bottom of the band crosses nearly all the head’s band, and of the pieces before it, the $i$-th piece crosses about $i/p$ of the tail. Averaged over $p$ pieces, the earlier pieces contribute about half the tail’s keys to each crossing and the head the whole of its band, so the pieces’ share approaches a half over one and a half, a third. With two pieces it is one in five by the same reckoning; the 24% measured is close.

That regularity explains the earlier rule’s failure pattern exactly. Leaving out a third of every crossing after the first should leave the price at about two thirds of the cost once there are many pieces, and the earlier rule’s ratio fell from 89% with two pieces towards 63% with 410. The two numbers are the same fact.

The searches that count the pieces’ keys grow as the square of the number of pieces: one at a 16th, 78 at a 128th, 83,845 at a 4,096th. Each is a binary search of a sorted piece of $b$ keys, about $\log_2 b$ comparisons, the search galloping makes when it pays, so at a 4,096th they cost about 335,000 comparisons, against 3.8 million moves for the sort. Where the choice is close, at a 128th and a 256th, they cost a few hundred searches; where they are many, at the smallest buffers, the choice was never close, and a rule could skip them by noticing that the head-only price already exceeds merging first.

As the tail reaches further #

As the late tenth is drawn from the top tenth of the keys up to all of them, the rule that prices each piece against the head it will meet chooses the cheaper end at all ten settings. The setting the earlier rule missed is the one where the original head holds no keys in the tail’s band, so that every key a piece crosses is another piece’s. Priced against the original head, the pieces looked almost free; priced against the head they will meet, they cost 5.95 moves a key by the rule’s estimate and 5.90 in fact, and the rule merges them first, at 4.33.

At the other extreme, the tail from the whole range of keys, the pieces’ crossings are almost all of original head keys, since the head holds nine tenths of every part of the range, and the two prices nearly agree: 98.1 moves a key priced against 97.2 paid at a 1,024th. The share that earlier pieces contribute falls as the head’s share of the band rises, which is the same arithmetic as before with the head’s band larger than the tail.

What the prediction got right #

The closing section predicted that each piece, priced at its true count of keys above its smallest, would come within 5% of its cost at every buffer, and that the rule would then choose the cheaper end at all seven buffers and all ten reach settings. The pieces come within 4% at six buffers and 6% at the seventh, and the rule chooses the cheaper end everywhere. It named two risks: the searches, about eighty thousand at a 4,096th, of which there are 83,845; and the table, which prices one run’s crossing and might not price many short ones, which it does to within 6% even at pieces of sixteen keys, and which the pieces turn out not to need, since a piece that fits the buffer costs exactly the shifts it makes once they are counted against the right head.

The question it asked was whether a sequence of merges can be priced as a sum of single merges once each is given the head it will really meet. On this input it can: a table measured once per buffer on single crossings of a static head, read at counts that one binary search per pair of pieces supplies, prices a hundred merges into a growing head to within a few per cent and makes every choice correctly. The earlier essay’s failure was a failure to count, and the counting is cheap where it matters.

What the price leaves out #

A head of fixed length in the table. The table is read for a head the length of the whole file, though the head a piece meets is shorter by the pieces still to come. At small buffers the shortfall at a 4,096th may be partly this; the table was not re-measured for each head length.

Pieces in their arrival order. The pieces go into the head in the order they were cut from the tail. Another order would change every piece’s count and the total, and nothing here asks which order is cheapest.

One file shape. A late tenth drawn from the top fifth of the keys, with the reach varied on two buffers. The third of every crossing that belongs to other pieces is a consequence of the head and the tail holding equal halves of the band; a tail from the top tenth puts the whole of every crossing after the first in other pieces, and the rule still prices it, because it counts rather than assumes.

Two ends only. As in the earlier essay, the rule chooses between sending every piece in and merging them all first.

Still open: every number of rounds, priced #

The rule now prices both ends of the choice correctly, and the earlier essays left the middle untested by prices: merging the pieces in rounds, pairs into fours, fours into eights, for some number of rounds short of all of them, and sending the groups that result into the head. How many pieces the head can afford found, by trying every number of rounds, that stopping partway was never the cheapest, and its own rule for choosing rounds, priced as shifts, was wrong in both directions.

The measurement that follows prices every number of rounds from the same two tables, the rounds’ cost from a measured merge of random pieces to that many rounds and each group’s crossing at the count of keys it will meet, and lets the rule choose the cheapest number, then compares it with the cost of every number tried. The prediction is that the priced rule never chooses a partway number at any buffer, matching the earlier essay’s finding that the ends are always cheaper, and that its estimate of every partway number lies within 6% of its cost. It could fail at the buffers near the crossing, a 128th and a 256th, where one round costs the pieces less than it saves the head on some inputs, and where the earlier essay’s single input may have hidden a partway optimum that a different seed of the tail would show. The question is whether the boundary between the ends is a sharp one, or a narrow band of buffers where merging a little is cheapest and no fixed rule of all or nothing can be right.