The rotation that could be priced

How many pieces the head can afford sorted a file that arrives almost in order: 65,536 keys, sorted except for a last tenth appended in random order from the top fifth of the keys. A stable sort with a buffer of $b$ keys can sort that tail a buffer’s worth at a time and then either send each sorted piece straight into the head, or merge the pieces among themselves to one group and cross the head once. Pieces that fit the buffer beat the library’s merge sort down to a buffer of a 128th, and below that the cheapest thing was to merge them all the way first. Merging partway, which the essay had proposed, was never the cheapest; the choice was between the two ends.

A rule that compared the two ends had priced both as shifts. Sending pieces in costs each piece’s size plus the head keys above its smallest, the moves a merge into the head makes when nothing rotates. Merging first costs two moves a tail key a round plus one crossing of the whole tail, priced the same way. That rule chose correctly everywhere but at a 128th, where it merged first and paid 3.55 moves a key when sending the pieces in cost 3.20. Its closing section found why: a group longer than the buffer crosses the head by the library’s rotation-based split, and rotation moves far more keys than shifting does. It proposed pricing that rotation from measurements of the library merge itself, a long run crossing a longer one at every buffer, and predicted that the priced rule would choose the cheaper end at every buffer and every reach of the tail measured, including the 128th. It named the risk that where the two ends are close, at a 64th, the price’s error might exceed their difference.

The rotation can be priced, and closely. The risk landed somewhere else.

Prices measured on runs the sort never sees #

The input, the buffers and the sort are the earlier essay’s, and every move is counted by the library merge’s own counter, so a move in a price is the same move the sort would make. The rule has two prices, both taken from runs of the library merge on synthetic inputs built for the purpose, never on the file being sorted.

The first is a crossing: one sorted run of $t$ keys merged into a sorted head of $n - t$ keys, when the run’s keys are spread at random among the head’s top $A$ keys and its own, at buffer $b$. It is measured on a doubling grid of $A$ from an eighth of $t$ to 64 times $t$, at each run length and buffer the rule needs, and read between grid points by interpolating in $\log A$. The second is the rounds: the moves of merging $\lceil t/b \rceil$ sorted pieces of $b$ random keys all the way to one group, at buffer $b$.

Before moving anything but the pieces’ own sorting, which both ends share, the rule reads each piece’s $A$ by one binary search of its smallest key in the head, the search a gallop from the end of a merge makes. It prices sending the pieces in as the sum of their crossings, and merging first as the rounds plus one crossing of the whole tail at the $A$ of the tail’s smallest key, and it takes the cheaper. Every calibration merge is checked sorted, and the sort’s own result sorted and stable.

The long crossing priced to within three per cent #

The measured price of the tail’s one crossing of the head comes within 3% of what the sort pays at every buffer: 2.23 moves a key of the file against 2.19 at a 1,024th, where pricing it as shifts says 0.20. The rounds before it are priced within 2%, 3.58 against 3.62 at a 1,024th, where two moves a tail key a round says 1.40. Shifts underpriced both, and by a factor that grows as the buffer shrinks: the crossing by a factor of eleven at a 1,024th and of two at a 16th.

The shifts price is the same at every buffer, 0.20 moves a key, because it counts each key the crossing passes once: the tail’s 6,554 keys and the 6,554 or so head keys above the tail’s smallest. The library merge does that only when the shorter side of a merge fits the buffer. When it does not, the merge splits the longer side, rotates the pieces into place, and recurses, and every rotation moves keys that a shifting merge would have left alone. The moves no stable sort can skip counted those rotations as the price of sorting stably in little space. A smaller buffer means more levels of splitting and more rotation, which is why the paid crossing rises from 0.45 to 2.69 moves a key from a 16th to a 4,096th while the shifts price stays flat.

A run of a tenth of the file crossing 16,384 head keys costs 6.76 moves a key of the run with a buffer of 4,096 and 38.4 with a buffer of 64. That is the table the rule reads. Each curve rises with the head keys the run interleaves with, as shifts would, and the curves separate by buffer, which shifts cannot: a run that the buffer cannot hold pays for every split it forces, and the number of splits grows as the buffer shrinks. Where the run interleaves with few head keys, 1,024 of them, a large buffer merges it at about a move and a third a key, which is shifting; a buffer of 64 already pays eight.

The table is measured on runs whose keys are spread at random over their range, the property of an input its runs describe, and the sort’s tail is exactly that, so the prices match closely. They match because the library merge’s work depends on how the two runs interleave and on the buffer, not on which keys they hold, and that is the condition under which a measurement on one input prices another.

The choice at a 128th comes right #

At a 128th the priced rule sends the pieces straight in, at 3.20 moves a key, where the shifts rule merged first and paid 3.55. The prediction’s named case comes right, and so does the case it named as a risk: at a 64th the two ends differ by half a move a key, 2.46 against 2.96, and the priced rule chooses the cheaper. Of the seven buffers it chooses the cheaper end at six.

The seventh is a 256th. There the pieces sent straight in cost 5.00 moves a key and the tail merged first 4.35; the rule prices them at 3.86 and 4.38 and sends the pieces in. Its price for merging first is right to within three hundredths of a move. Its price for sending the pieces in is a quarter too low.

The shifts rule was right at a 256th, and for no good reason. It priced sending the pieces in at 2.69 moves a key and merging first at 1.20, leaving out the pieces’ own sorting, and both were far below what the sort paid; the two errors were of different sizes, and here they happened to point the way that made the choice right. A rule whose errors are large can be right by luck at one buffer and wrong at the next, which is what it was at a 128th. The priced rule’s error is confined to one of its two prices, and it is wrong exactly where that price’s error exceeds the gap between the ends. The prediction expected the risk to lie in the crossing it could not price; the error is in the crossings it thought it could.

What the pieces cross #

The pieces’ crossings are priced at 89% of what they cost at a 16th, 74% at a 128th and 67% at a 1,024th: the price falls further behind the cost the more pieces there are. Each piece is priced against the head as it stood before any piece joined it. But the pieces go in one after another, and the head a piece meets holds every piece merged before it. Those pieces are drawn from the same top fifth of the keys, so a piece crosses not only the original head’s keys above its smallest but also most of the keys of the pieces already merged, and that second count grows with the number of pieces in front of it.

At a 16th there are two pieces and the second crosses one piece’s worth of extra keys; the price is short by a tenth. At a 1,024th there are 103 pieces and the last of them crosses the keys of a hundred others; the price is short by a third. The crossing table is right about what one crossing costs given its $A$. The rule fed it the wrong $A$, the one it could read off the head before moving anything, and every $A$ after the first is larger by the keys of the pieces already in.

As the tail reaches further #

As the late tenth is drawn from the top tenth of the keys up to all of them, the priced rule chooses the cheaper end at nine of the ten settings at a 1,024th and a 128th, and the shifts rule at eight. The one setting the priced rule misses is the one where the pieces cross the original head least: a tail of a tenth of the file drawn from the top tenth of the keys is the whole of that tenth, so the original head has no keys above any piece, and at a 1,024th every one of the 103 pieces crosses only the pieces merged before it. Priced against the original head alone, sending them in looks almost free, 0.76 moves a key of the file with the pieces’ own sorting included; it costs 5.90.

The further the tail reaches, the more of each piece’s crossing is of original head keys, and the closer the price comes. With the tail from the whole range, the pieces cost 97 moves a key at a 1,024th and are priced at 93; nothing about that choice is close, and both rules make it.

What the rotation was, and what it was not #

The earlier essay’s closing section treated the rotation as the part of a merge a sort could not price without doing it, as a request that reads the input first had priced buffers from the runs it found rather than from the moves they would cost. Measured once per buffer on synthetic runs, it can: the crossing of a long group, which is almost all rotation at small buffers, comes within 3% at every buffer, and the rounds within 2%. The library merge’s cost depends on the buffer, on the run lengths and on how the runs interleave, and a table indexed by those three numbers carries it from one input to another. Pieces that fit the buffer began this strand by noticing that a merge that fits the buffer costs about shifts and one that does not costs much more; the table is that observation made exact.

What the rule could not price is the sequence. Sending the pieces in is not seven or a hundred independent crossings of one head; it is a hundred crossings of a head that each crossing enlarges. The rule’s price treated them as independent, and its error grew with how many there were. That is the error that made it wrong at a 256th and at the shortest reach, and it is an error in what was counted, not in the price of any one merge.

What the prediction got right #

The closing section predicted that pricing the rotation from measurements of the library merge would let the rule choose the cheaper end at every buffer and every reach measured, including the 128th where the shifts rule chose wrongly, and so cost the cheaper end everywhere. It chooses correctly at the 128th, at six of seven buffers and at nine of ten reach settings. It named the risk that at a 64th the two ends are close and the price’s error might be larger than their difference. At a 64th the rule is right; the difference there is half a move, and the price of the end it rejected is right to the hundredth.

The rule fails at a 256th and at a 1,024th with a short reach, both times by pricing the pieces sent straight in too low, because each piece crosses the pieces before it as well as the head. The question the section asked, whether the rotation a merge will do can be priced without doing it, has a plain answer: yes, from a table measured once per buffer. The measurement the sort could not afford to take was not the rotation. It was how many keys each piece would find in front of it once the pieces before it had joined the head.

What the prices assume #

Runs spread at random. Every calibration run’s keys are spread uniformly over their range, and so are the tail’s. A tail whose keys cluster would cross a head differently from the table’s runs, and the prices would have to be measured on clustered runs to match.

One file size. The table is measured for the file’s own length and the tail’s, and read between grid points in the head keys above. A sort of a different size would need the table at its own lengths.

Two ends only. The rule chooses between sending every piece in and merging them all first, because the earlier essay found that stopping partway was never the cheapest. The same two prices could price every number of rounds, and nothing here tests whether a priced rule would find a partway point that the earlier essay’s estimates missed.

Moves only. The prices count moves, as the earlier pages did. The binary searches that read each piece’s position and the calibration’s own merges are not charged to the sort; the calibration is done once per buffer and file size, and the searches are a few comparisons a piece.

Still open: pieces priced against the head they will meet #

The pieces’ price was short by the keys of the pieces merged before each one. Those keys are known before anything is merged: the pieces are already sorted, and the number of keys in an earlier piece above a later piece’s smallest is one binary search of that earlier piece. A piece’s true $A$ is the original head’s count above its smallest plus the sum over earlier pieces, and with that $A$ the same table should price each crossing as closely as it prices the tail’s.

The measurement that follows prices each piece at that $A$, the head’s count plus the earlier pieces’ counts, and repeats every buffer and reach. The prediction is that the pieces sent straight in are then priced within 5% at every buffer, so that the rule chooses the cheaper end at all seven buffers and all ten reach settings. It could fail on the order of the pieces. The searches cost a binary search of every earlier piece for every piece, which at a 4,096th is 410 pieces and eighty thousand searches, and it could fail on the table: a piece that fits the buffer merges by shifting, and if its crossings of earlier pieces scatter it through the head in a way a single run’s crossing does not, the table’s price for one run may not hold for the many short crossings a piece makes. The question is whether the sequence of merges can be priced as a sum of single merges once each is given the head it will really meet, or whether merging pieces one after another is a different process from merging one of them.