How many pieces the head can afford

Pieces that fit the buffer sorted a file the merge sort finds awkward. Sixty-five thousand keys arrive sorted, and then a late tenth arrives in random order, drawn from the top fifth of the keys. The buffered stable merge sort — the library’s merge, which works in a buffer when the shorter of two runs fits and by rotation when it does not — spends two thirds of its moves sorting the late tenth among itself, a dozen levels of merging over 6,554 keys. The earlier page took the tail a buffer at a time instead, sorted each piece, and merged each sorted piece into the head from the right. At a buffer of a 64th of the file the pieces won, by removing the final merge’s rotation. At smaller buffers they lost, because each piece’s merge into the head crosses the head’s top fifth again, about 0.15 moves a key of the file a crossing.

Its closing section saw the two buffers as two ends of one choice. A sort could merge the pieces with each other before merging them into the head: four pieces merged pairwise and then into the head cross the head half as often as four pieces would, and pay one more level of merging inside the tail. Both prices are known before they are paid. A level of merging inside the tail costs about two moves a tail key; a crossing costs about the number of head keys above the group’s smallest key, which one binary search in the head finds. The proposal was a rule — merge the pieces among themselves while one more round costs less than the crossings it removes, then merge what is left into the head. It predicted that at a 64th the rule merges the seven pieces once and saves a little more than the pieces already save, and that at a 1,024th it merges the 103 pieces down to four or eight and comes within a fifth of the merge sort. It named the failure: merged groups are larger than the buffer, and their merges into the head rotate again.

The sort, counted by the library’s own merge #

The input is the earlier page’s: 65,536 distinct keys, the first nine tenths sorted, the last tenth drawn at random from the top fifth of the keys and appended in random order. The sort finds the head by a scan. It sorts each piece of the tail in place — binary insertion into runs of eight, then merges that fit the buffer, as a library sorts a short array and for the reason where insertion sort actually wins measured — then runs some number of rounds, each merging adjacent groups of the tail in pairs, and finally merges each remaining group into the head. Every merge is the library’s: trimmed by galloping from both ends, the step the skip the split already made added, done in the buffer when the shorter side fits, and split by binary search and rotation until it fits when it does not. Every move is counted by the same counter that counted the merge sort, so the two are on one scale; counting rather than timing is what lets a twentieth of a move a key be a finding, the practice counting instead of timing set out. Sorting the pieces this way costs a little more than the earlier page’s — 2.46 moves a key at a 64th against its 2.41 — and the comparison here is between round counts, all of which share it.

The rule is the proposal’s. Before each round it prices the round at two moves a key of the tail. It prices the crossings the round removes, for each pair of groups, at the head keys above the larger of the two groups’ smallest keys — the later group’s crossing, which the pair would no longer make separately — found by one binary search in the head. It takes the round while the crossings cost more.

Thirteen pieces and not twenty-six #

Sent straight into the head, pieces that fit the buffer beat the merge sort down to a buffer of a 128th — 3.20 moves a key against 3.54, with thirteen pieces — and lose from a 256th, with twenty-six; below that, the cheapest sort is the pieces merged all the way to one group first, which costs the merge sort’s moves to within six hundredths. The rule matches the cheaper end only at the two largest buffers, where it takes no rounds. At a 64th it takes one round and costs 2.75 against the pieces’ 2.46; at a 1,024th it takes five and costs 7.68 against 6.46.

The prediction for a 1,024th was that the rule comes within a fifth of the merge sort, and 7.68 against 6.45 is 19% over, so it holds by a hair. The prediction for a 64th fails: one round makes the pieces worse, not better. And the plate’s larger shape is not one either prediction imagined. There is no buffer at which merging part of the way is the cheapest thing to do. Each buffer has two candidates, no rounds and all of them, and the cheaper of the two changes between a 128th and a 256th.

That the all-rounds sort is the merge sort to within six hundredths is less of a coincidence than it looks. Merging the tail’s sorted pieces all the way to one group is the merge sort’s own schedule applied to the tail alone, and merging that one group into the head is the merge sort’s last merge. The only difference is that the merge sort’s schedule merges the shortest runs first and may merge some of the head’s runs with the tail’s on the way; on a file whose head is one run it has nothing to merge the head with until the end.

The first round always costs more #

At every buffer the first round of merging inside the tail costs more than none: at a 1,024th it raises the cost from 16.04 moves a key to 18.97, at a 256th from 5.00 to 5.79, at a 64th from 2.46 to 2.75. After the first, each round lowers the cost at the two smaller buffers, and the curve falls below the pieces’ own cost only from the second round at a 1,024th and the third at a 256th, reaching the merge sort’s level when the rounds run out. At a 64th every round costs more than the last.

The shape is a bump, and its cause is the buffer. A piece is exactly one buffer long, so after the first round every group is two buffers long, and a merge of a group into the head no longer has a shorter side that fits the buffer — the head is far longer, and the group is longer than the buffer too. The library’s merge then splits it by binary search and rotates the parts into place, and rotation moves the head’s keys that lie between the split points, sometimes more than once. Before the round, each piece crossed the head by shifting the head keys above its smallest one place along; after it, each group crosses by rotation, which costs more than the shifts of the two pieces it replaced.

The rounds that follow lower the cost because they reduce the number of groups that cross, and every crossing costs rotation. At a 1,024th, after seven rounds there is one group: one crossing, by rotation, for the whole tail. That one rotation is the merge sort’s own rotation, 4.54 moves a key here against its 4.58, which is the earlier page’s finding again from the other side. The pieces won at a 64th by removing the final merge’s rotation; at small buffers the rotation cannot be removed, only made to happen once.

Where the moves go #

At a buffer of a 1,024th the merges into the head are almost the whole cost with no rounds — 15.39 moves a key of 16.04 — and once a group outgrows the buffer, most of a head merge is rotation: 10.38 of 18.31 after one round. The pieces’ own sorting is 0.65 at every round count. The first round inside the tail costs 0.15 moves a key of the file, a move and a half for each tail key, near the proposal’s two; the later rounds cost more, 0.94 a key of the file for the seventh, because they merge groups larger than the buffer and rotate too, and all seven together cost 3.62. The proposal priced the first round about right and the crossings as shifts, and with no rounds the second is right as well: 103 pieces each shifting a few thousand head keys is 15.39 moves a key.

After one round the shifts are gone and rotation has replaced them. Fifty-two groups of 128 keys each cross by splitting and rotating, and each rotation moves the head’s keys above the group’s split point as a block, with a buffer of 64 to help. The 10.38 is what fifty-two such crossings cost. The rule did not see it because a binary search in the head says how many head keys a group will pass, not how the library’s merge will pass them, and the answer depends on whether the group fits the buffer — which the group the round has just made, never does.

What the rule expected #

The rule’s estimate of a round is wrong both ways: at a 1,024th it expects the first round to save 4.78 moves a key and the round costs 2.93; it expects the fifth to save a tenth of a move and the round saves 1.48, and the sixth nothing when it saves 0.84. It stops after five rounds, at 7.68, where two more would have reached 6.46. At a 64th it expects the first round to save a tenth of a move a key, takes it, and the round costs 0.28.

Both errors come from the same omission. The rule counts a crossing’s head keys and never asks whether the crossing will rotate. On the first round it believes it is removing shifts, when it is replacing them with rotation. On the later rounds it believes the remaining crossings are cheap shifts of a few head keys each — the estimate falls because the pairs’ smallest keys are high — when each is a rotation whose cost is set by the size of the group as well as the head keys it passes, and removing one removes a large cost. A rule that knew how the merge would cross would see the bump and the long fall after it. Knowing that is knowing the library’s merge, and the earlier pages measured that a rotation-based merge’s cost depends on the split points it chooses, which is not something one binary search can price.

The reach of the late tenth #

At a buffer of a 1,024th, the further the late tenth reaches into the file the worse the pieces do — 5.90 moves a key when it is drawn from the top tenth, 97.19 when it is drawn from anywhere — and the rule ties the merge sort from a reach of two fifths on only because it then merges all the way. At a reach of a tenth it takes no rounds and pays 5.90 against the merge sort’s 4.31, the same mistake from the opposite side: there the pieces’ crossings are short, the rule sees them cheap, and they are, but 103 of them still cost more than one merge sort.

The reach sets how many head keys every crossing passes. A tail drawn from the top tenth crosses a tenth of the head at most; one drawn from anywhere crosses all of it, on average half. With 103 pieces each crossing half the head, the pieces cost nearly a hundred moves a key; the merge sort crosses once and costs fifteen. A reach of a fifth, the earlier pages’ input, is near the point where the two kinds of cost meet, which is why that page’s best buffer was a narrow win.

What the head can afford #

The question the proposal asked was how many pieces the head can afford, and the measurement answers it directly: at a reach of a fifth, thirteen, and not twenty-six. Below a buffer of a 128th there are too many pieces for each to cross separately, and there is no way to cross a few times rather than many without crossing by rotation. Merging the pieces into larger groups trades each piece’s cheap crossing for a group’s expensive one, and the trade pays only when it is taken all the way, to one group and one crossing, which is the merge sort.

The buffer a schedule cannot bend found that a merge schedule chosen to fit a buffer still meets merges that do not fit it, and pays rotation for them. The pieces are the same lesson at the tail’s scale: a schedule can arrange for many small merges that fit or one large one that does not, and the many fit only while there are few enough of them. A merge sort with a small buffer is cheap for the reason the pieces are dear — it crosses the head once — and the moves no stable sort can skip measured how far above the floor that single crossing still is, fifteen times at a 64th.

A simpler rule shows how close the boundary sits to the estimates. Comparing only the two ends — every piece crossing at its estimated shifts, against every round at two moves a tail key and one crossing of the whole tail, also priced as shifts — picks the cheaper end at every buffer but one. At a 128th it chooses to merge everything and pays 3.55 where the pieces cost 3.20, and at a 64th it chooses the pieces by an estimated margin of 54 moves in 52,000, where the true margin is 32,000. It is right there by luck. It prices the one crossing that rotates as if it shifted, and that crossing is most of the merge sort’s cost.

So the choice for a late tail is binary and the boundary is computable in advance from two numbers the sort can know: the number of pieces, which is the tail’s length over the buffer, and the head keys each piece will pass, which one binary search a piece finds. Below the boundary, send the pieces straight in. Above it, sort the tail as a whole. The rule that tried to find an interior point found the worst of both.

What this file leaves out #

One input shape. The head is one run and the tail is random within its reach, a shape a run is a property of the input would describe by its two runs’ lengths and nothing else. A tail that arrives partly sorted, or a head that is several runs, would change both costs, and the merge sort’s schedule would have more to merge before the end.

One way to sort a piece. Each piece is sorted by insertion into runs of eight and merging, a library’s method for short arrays. The earlier page’s alternative, the buffered merge sort on the piece alone, costs a twentieth of a move a key less at a 64th and would move every curve here down by that much without changing their shape.

Moves only. Every cost here is moves, the quantity a buffer-limited merge spends where the floor a merge cannot reach counted comparisons. The binary searches and the galloping trims cost comparisons, which are counted but not reported, and are a small fraction of the moves at every setting.

Still open: a boundary priced in advance #

The boundary between the two ends is a comparison the sort can make before it moves anything. The pieces’ cost is about each piece’s size plus the head keys above its smallest, summed — the rule’s own crossing estimate, which is right when nothing rotates. The merge sort’s cost on the tail is about two moves a tail key a level of its schedule, plus one crossing of the whole tail by rotation, and the rotation’s cost is the part the rule had no way to price.

The measurement that follows prices that rotation from the head’s length, the tail’s length and the buffer — measuring the library merge’s rotation cost for one long run crossing a longer one at every buffer — and gives the sort a rule that sends the pieces straight in when their summed crossings cost less than the merge sort’s estimate, and sorts the tail as a whole otherwise. The prediction is that it chooses correctly at every buffer and every reach drawn here, including the 128th where the ends rule, which priced the single crossing as shifts, chose wrongly, and so costs the cheaper end everywhere, 3.20 at a 128th and 6.45 at a 1,024th. It could fail where the two ends are close: at a 64th they differ by half a move a key and the estimate’s error may be larger than that. The question is whether the rotation a merge will do can be priced without doing it, or whether the merge’s cost at the boundary is a measurement a sort cannot afford to take.