The buffer a schedule cannot bend

A request that reads the input first gave a stable merge sort one pass over its input before it asked for any memory. The pass found the natural runs, and the moves fell with them: 2.80 a key on four long runs against 17.2 for libstdc++'s std::stable_sort, and none on sorted input. The buffer did not fall. Asked for as the largest merge’s shorter run, it came to between 36% and 45% of the input on everything from two runs to 4,096, against the library’s half. A balanced schedule merges runs in pairs, then pairs of pairs, and its last merge joins two halves of the file whatever the runs looked like.

That essay closed by turning the question round. The schedule is a choice, and the sort that has read the runs knows enough to make another. Set the buffer first — a quarter, an eighth, a sixteenth of the input — and choose a schedule whose every merge fits, using rotation for any merge that cannot. The prediction was that on a few long runs a sixteenth would cost little, because the long runs could be merged last against short neighbours, and that on random keys the sort would cost what the library costs at a sixteenth. The question was whether reading the input lets a sort set its memory by the input’s disorder rather than its length.

Two schedules and a split #

The sort is the earlier page’s, with the minimum run of eight that page found better for moves than thirty-two — one of the constants the threshold somebody chose found reasonable and underived in every library that carries one. One pass finds the maximal non-decreasing runs, and runs shorter than eight are extended by binary insertion. The merges are then scheduled in one of two ways. Balanced rounds is the earlier page’s schedule: adjacent runs in pairs, round by round. Smallest-first repeatedly merges the adjacent pair whose shorter run is shortest, so every merge that fits the buffer is taken before any merge that does not. It is the greedy form of what the proposal described, and it is close to what Timsort’s merge rules aim at, keeping pending runs of balanced size so that merges stay cheap.

A merge whose shorter run fits the buffer copies that run into the buffer and merges from it, as the library’s buffered merge does. One that does not fit is split. The library’s own routine for that case halves the longer run, finds the matching cut in the shorter one by binary search, rotates the middle so that both halves’ pieces are in place, and recurses on the two halves until each piece fits. The rotation moves keys without merging anything. A guarantee that depends on an allocation found that path carrying the library’s sort when its buffer request fails, and it is the same code here, chosen deliberately.

The inputs are the earlier page’s: 65,536 keys made of four, sixteen, 256 or 4,096 ascending runs of random lengths, a sorted file with a tenth of new keys appended in random order, and random keys. Every sort is checked sorted and stable, and moves and comparisons are counted as before, every element assignment a move.

What a buffer set in advance costs #

On four long runs, a buffer of a sixteenth costs 8.70 moves a key against 2.80 with room for every merge — three times as many. A quarter costs 3.53, an eighth 5.70, a sixty-fourth 14.7 and a 256th 20.9. The prediction said a sixteenth would cost little, and it costs three times the moves. It is still half the library’s 17.2 at its full request of half the input, and under two fifths of the library’s 22.9 at the same sixteenth. The run-reading sort moves fewer keys than the library at every buffer measured, down to a 256th.

On random keys the run-reading sort costs what the library costs, within 14% at every buffer. At a sixteenth it moves 28.4 keys a key against the library’s 27.2, and at a 256th 60.6 against 60.5. That part of the prediction holds. Random keys have runs two keys long, the pass finds nothing worth knowing, and both sorts are then merge sorts over the same buffer with the same rotations.

Every extra move is a rotation #

At a sixteenth of the input, the merging and buffering moves are exactly what they were with room for every merge; everything added is rotation. On four runs the rotations cost 5.90 moves a key, on sixteen 7.43, on 256 8.50, on 4,096 7.29 and on random keys 7.45. The merging itself costs 2.00 on four runs and 13.0 on random keys, the log of the number of runs as before. At a sixteenth the rotation cost barely follows the runs. It sits between six and eight and a half moves a key on every input but one, and it is set by the buffer.

That is why the prediction failed. It pictured the long runs merged last against short neighbours, so that only the final merges would outgrow the buffer. On four runs of random lengths there are no short neighbours. The four runs average 16,384 keys, every merge in any schedule joins two pieces of thousands of keys, and all three merges are split. A split merge of $m$ keys with a buffer of $b$ recurses until its pieces fit, about $\log_2(m/b)$ levels deep, and each level rotates up to the whole merge’s width. With a buffer of a sixteenth, that is a few levels of rotation over most of the file, whatever order the merges came in.

Below a sixteenth the inputs separate. At a sixty-fourth, rotation costs 11.9 moves a key on four runs and 20.2 on random keys; at a 256th, 18.1 and 39.7. Each halving of the buffer adds a level of splitting to every merge too large for it, and random keys have more rounds of merges large enough to be split: about thirteen rounds over the whole file against two on four runs. Four runs add about three moves a key in rotation for each halving below a sixty-fourth, and random keys about ten. Still, the buffer decides whether rotation is paid at all, and the runs decide how many times.

So the two costs add. Reading the runs sets the merging cost, the buffer sets the rotation cost, and neither changes the other. The one input where the rotations nearly vanish, the sorted file with a tenth appended, costs 0.55 moves a key in rotation. It is different because of what the schedule can do there, not the buffer.

What the split costs in comparisons #

A split merge finds its cut by binary search, and the searches are the only comparisons a rotation adds. They are almost free. On four runs the sort makes 3.00 comparisons a key with room for every merge and 3.03 at a 256th of the input; on random keys, 15.96 and 16.07. The library makes 10.2 comparisons a key on four runs and 15.8 on random keys at every buffer. So on an input with long runs, reading the runs first saves two thirds of the comparisons and most of the moves, and a small buffer takes back only moves.

That matters for which cost a caller should watch. A run is a property of the input found the number of natural runs predicting a presorted input’s comparison count better than any recipe for making presorted data. The same count predicts the comparisons here at every buffer. The moves it predicts only when the buffer is large enough for the merges, and below that the buffer predicts them too. The order equal keys keep is the reason none of this can be bought more cheaply by giving up stability: a rotation is how a merge with no room to copy keeps equal keys in the order they arrived, and that order is what the caller of a stable sort paid for.

No order of merges avoids two large pieces #

Merging smallest-first needs 45% of the input on four runs, 43% on sixteen and 41% on random keys to avoid every rotation — about what the balanced schedule needs, and on 4,096 runs more, 43% against 36%. The last merge of any schedule joins two pieces that together are the whole file. Its shorter piece is as small as the schedule can make it only if one side can be kept small to the end, and that requires a run that is most of the file. With runs of comparable length, the two final pieces are comparable too, whatever order built them. Smallest-first can shift which merges are last, and it does lower the need on 256 runs, 35% against 42%. It cannot make the last merge lopsided when the input is not.

The sort’s memory is therefore set by the shape of its largest runs, and a schedule can only choose among a few orders of the same pieces. Disorder in the sense the earlier page measured, the number of runs, does not enter it. The proposal’s hope, that reading the input would let the memory follow the disorder rather than the length, is met only where the input’s disorder is concentrated in a small part of it.

Where the schedule matters #

On a sorted file with a tenth appended, merging smallest-first costs 2.71 moves a key at every buffer down to an eighth, and balanced rounds cost 10.4. Here the input has one run that is 90% of the file and a tail of short runs. Smallest-first merges the tail’s runs among themselves until they form one run of a tenth of the file, then merges that once into the long run. Its largest merge’s shorter side is the tail, 10% of the input, and a buffer of an eighth holds it. Balanced rounds pair the long run with the first short run next to it in the first round, then with the result of the next pair, and so on. The long run is merged again in every round, and each round moves most of the file. Its largest shorter side is smaller, 3.4%, but it pays for that in moves four times over.

At a sixteenth the smallest-first sort splits only its last merge and costs 3.26 moves a key; at a sixty-fourth, 6.56. The library, which reads nothing, costs 16 to 19 at every buffer. This is the case the earlier page found the request falling on, and it is where choosing the schedule, not only sizing the buffer, pays: by a factor of four at the same buffer. When galloping pays found galloping worth having on inputs of exactly this shape, and a merge that gallops over the long run’s untouched stretches would cut the 2.71 further. Galloping was not modelled here.

The margin over a sort that does not look #

Reading the runs first moves 16% of the library’s moves on four runs with room for every merge, and 58% at a 256th of the input. The margin narrows as the buffer shrinks because both sorts pay about the same rotations, and a shared cost that grows dilutes a fixed saving. It never closes on any input made of runs. On 4,096 runs the margin is 4% throughout, since runs sixteen keys long leave the pass little to find. On random keys the run-reading sort is up to 14% worse, at a quarter, and level with the library at the smallest buffers.

That is the practical form of the answer. A library that reads its input first and is handed a small buffer — because the allocation failed, or because the caller set a budget — loses none of the advantage the pass gave it, beyond what the rotations dilute. The request no price of memory would make found the library’s own request of half the input on no memory price’s best line. This page’s numbers say a sort that has read the runs can live on a sixteenth of the input and still move half what the library moves at a half, on inputs of a few long runs.

What was wrong in the picture #

The proposal’s picture of a schedule came from inputs it imagined: long runs with short neighbours, where the order of merges decides which pieces meet the buffer. Random run lengths do not look like that. Four cuts at random positions make four runs of comparable size, and the same is true of sixteen or 256. The only common input with the imagined shape is a long run with a short tail, and there the picture was right.

The sort the library ships found every major runtime but C++ sorting objects with a sort that reads runs first. The results here add one point to that. Those sorts also merge in an order chosen from the runs, and the choice mattered here only on appended data. Everywhere else the rotations set the price of a small buffer, and rotations are the same code in every library.

Where the measurement stops #

Moves, not time. Every number is an element move. A rotation moves keys in long sequential sweeps and a merge interleaves two sources, so a timed comparison could weigh the two differently. Counting instead of timing is why the counts are what is reported.

Two schedules. Smallest-first is a greedy rule. A schedule chosen by searching over merge trees for the fewest moves at a given buffer might do better on 256 runs, where the greedy rule already lowers the need. It was not searched for.

One draw of run lengths an input. Each input with $k$ runs is one draw of random cut points. On four runs, a draw with one very short run would give smallest-first something to merge early; the draw here has runs of 16%, 29%, 35% and 19% of the file, none short enough to merge early.

One input size. Every measurement is at 65,536 keys. A split merge’s depth follows the ratio of the merge’s width to the buffer, so a larger file with the same share of buffer should split each merge to the same depth, and one with the same absolute buffer should split deeper. Neither was run.

No galloping and no descending runs. As before, the pass finds non-decreasing runs only, since reversing a run could reorder equal keys, and no merge gallops.

Still open: a rotation that knows the runs #

Every extra move a small buffer causes is a rotation, and the library’s rotation is a generic one. It halves the longer run, binary-searches the shorter, rotates the middle and recurses, as if the two runs were arbitrary. A sort that has read its runs knows more than that about the two sides of a split merge. It knows where the natural runs inside each side began, and whether a long stretch of one side falls entirely before or after the other side’s keys.

The measurement that follows gives the split a first step: before halving, find by galloping how much of each side is already in place against the other, and exclude it from the rotation. The prediction is that on inputs of a few long runs with random values, which interleave everywhere, this saves almost nothing, since little of any side is already in place. On inputs whose runs overlap only at their ends it should remove most of the rotation cost. That includes a sorted file with a batch of late keys, or runs that were themselves sorted batches of increasing keys. The number that decides it is the share of each split merge that galloping can set aside. It is also the share of the input that a stable sort with a small buffer never needed to move at all.