The moves no stable sort can skip

The skip the split already made gave a buffer-limited stable merge sort a trim. Before each merge, gallop in from both ends and set aside whatever is already in place against the other run, so that only the overlap is merged. On sixteen sorted batches each overlapping the next by 5%, the kind of file written in batches by time with a few late records in the next batch, the trim took the sort to 0.13 moves a key and made it flat in the buffer: the same 0.13 whether the buffer was a quarter of the input or a 256th. Without the trim, a larger buffer moved more, because each buffered merge copies its whole shorter run.

The essay closed by asking how close 0.13 is to the least any stable sort could manage. Moves have a simple floor: a key whose final position differs from where it starts must be moved at least once. The section reasoned that the trimmed sort moves each overlap’s shorter side twice, into the buffer and back, and the longer side once, and predicted that the floor would be about two thirds of the trimmed sort’s count. It predicted the trimmed sort within a factor of two of the floor on batches and on sorted files with a late tail at every buffer, and several times the floor on runs of random values, where nearly every key is out of place and a rotation moves each key many times. Where the factor is largest is where a stable sort is doing the most work no algorithm needs.

Half of that holds exactly. The other half fails on an input whose cost turns out to be somewhere the prediction did not look.

A floor made exact #

Every input here is 65,536 distinct keys, so each key’s final position is its rank, and the input is a permutation: the key at position $i$ belongs at position $x_i$. A key with $x_i = i$ need never move. Every other key must be written at least once. That count alone is not quite the least, because writing a key into its place overwrites whatever was there, and a sort needs somewhere to hold it. A permutation is a set of cycles: the key at $i$ goes to $x_i$, whose key goes to $x_{x_i}$, and so on back to $i$. A cycle of $L$ keys can be put right with one spare cell in exactly $L + 1$ moves: save one key, move the other $L - 1$ along the cycle, put the saved one in the last place. A swap of two keys is a cycle of two and costs three moves.

So the floor is the displaced keys plus one move for every cycle of two or more. No sort with one spare cell can do with fewer, whatever it compares. A sort that knew every key’s rank before it moved anything would reach the floor exactly by following the cycles; the floor is a property of the input, and the question is how far a comparison sort that must discover the ranks as it goes falls above it.

On these inputs the cycles add almost nothing: under a hundred moves against thousands of displaced keys. Sixteen overlapping batches displace 8.9% of their keys in 85 cycles, so the floor is 0.090 moves a key. A sorted file with a late tenth appended from the top fifth of the key range displaces 20.0%. Every input with random values in it displaces essentially every key, in a handful of long cycles, and its floor is 1.00.

Two thirds, and for the reason given #

On batches that overlap by 5%, the trimmed sort moves 0.131 keys a key against a floor of 0.090, 1.46 times the least possible; from 1% overlap to 25% the factor stays between 1.40 and 1.49. The prediction said the floor would be about two thirds of the trimmed sort’s count. It is 0.69 of it, and the reason holds as stated. Where two batches overlap, the merge copies the overlap’s shorter side into the buffer and merges back, writing those keys twice. The longer side’s overlapping keys are written once. When the two sides are about equal, as they are here, that averages to one and a half moves for each displaced key, which is the 1.46. The half move above the floor is not the buffer’s size but its use: copying out and merging back is what any sort that merges through a buffer pays, and the trim made it pay that only for the overlap.

Past a quarter the factor grows: 2.23 at half overlap and 2.67 when each batch overlaps the next entirely. A batch then shares half its range with each neighbour and has little in place to trim, and the trimmed sort moves about what the untrimmed one does, 2.50 keys a key against 2.48: the moves of merging sixteen runs over four levels, against a floor that counts each key once. The untrimmed sort is 25 times the floor at 1% overlap, since it copies whole runs to merge a few keys at their ends.

Flat in the buffer, until the overlap no longer fits #

On batches the trimmed sort is 1.46 times the floor at every buffer from a quarter of the input to a 256th, and 3.5 times at a 1,024th. A 1,024th of 65,536 keys is 64 keys, and a 5% overlap between batches of 4,096 is about 205 keys. Once the overlap no longer fits in the buffer, the merge must split it by rotation, and every rotation moves keys that are already where the floor would leave them. The buffer the trimmed sort needs is set by the overlap, not by the file. Above that size the buffer buys nothing, which is what flat in the buffer meant on the earlier page.

Every other input is several times the floor at every buffer, and the factor grows as the buffer shrinks. On four runs of random values it is 3.5 times at a quarter and 27 times at a 1,024th. The prediction said several times, and at small buffers it is several tens. The buffer a schedule cannot bend found every extra move a small buffer causes to be a rotation, and the rotations are what climb: a merge of two long runs that cannot be buffered is split in half, the halves rotated past each other, and each half merged again. On random keys a sort writes 21 to 85 times the floor. Those are the costs of merge sorting a random file, and the floor of one move a key is far below them.

The climb can be divided exactly, because the sort counts its moves by kind. On four runs of random values, the buffered merging costs 2.80 moves a key at a 16th, a 64th and a 256th alike: the same three merges of runs, each copying its shorter run to the buffer and back. Everything above that is rotation, 5.9 moves a key at a 16th, 11.9 at a 64th and 18.1 at a 256th. Each halving of the buffer adds a level to the recursion that splits a merge too large to buffer, and every level rotates most of the keys once more. So the part of the sort a buffer can pay for sits at 2.8 times the floor on this input. The rest is the price of not having the buffer, and the floor does not see it at all, since a sort that knew its ranks would need no buffer to place a key.

The late tenth, predicted within twice #

A late tenth drawn from the top fifth of the key range costs the trimmed sort 2.93 moves a key at a 64th buffer, against a floor of 0.20: 14.6 times the least possible, where the prediction said under two. The factor is largest when the late keys are latest. Drawn from the top tenth of the range they displace a tenth of the file and the sort moves 19.7 times that; drawn from anywhere they displace everything and it moves 6.5 times.

The floor is small for a late tail because a late key belongs near the end, and only the keys it must pass are displaced. The prediction treated the late tail as an overlap: one merge between a sorted head and a tail that interleaves with the head’s top fifth, costing about one and a half moves for each key in the overlap, as the batches do. That would be about 0.3 moves a key. The measured cost is ten times that, and the prediction’s model of the input is what failed. A late tenth is not one sorted run. It is 6,554 keys in random order, and before it can be merged into anything it has to be sorted.

Two thirds of the work in a tenth of the keys #

Sorting the late tenth among itself costs 1.89 of the 2.93 moves a key at a 64th buffer, 18.9 moves for each late key; merging the sorted tenth into the rest costs the other 1.04. The tenth is a random file of 6,554 keys, and a merge sort moves each key of a random file about one and a half times for every level of merging, a dozen levels here. A larger buffer does not change that: at a quarter of the input, more than enough to buffer every merge, the tenth still costs 15.9 moves a key, because a merge sort’s moves are a logarithm of the run count however much room it has. The floor a merge cannot reach found the comparison floor out of reach for a merge, and the move floor is further out of reach, since a merge writes every key it merges at every level whether or not it ends up anywhere new.

The merge of the sorted tenth into the head is the part the prediction priced, and it is 1.04 moves a key at a 64th, five times the floor of the whole file, not the one and a half the batches gave. The tail’s keys interleave with the head’s top fifth, 13,107 keys, and the merge at that buffer is split by rotation, with the same climb the runs of random values showed. At a quarter, where the merge is buffered, it costs 0.30, about one and a half times the floor, as the prediction said for the merge alone.

The library beside the trimmed sort #

The library’s stable sort moves 130 times the floor on batches at a 64th buffer and 41 times on random keys, where the trimmed sort moves 1.5 and 41. On random keys the two sorts are the same distance from the floor, since neither can do better than merge sort’s levels there. Everywhere else the library is further away, and furthest on the input that needed least. The library sorts every input as though it were random: it cuts the file into chunks of seven, sorts each by insertion, and merges the chunks level by level, so on batches that are nearly sorted already it moves every key a dozen times. Where insertion sort actually wins measured the chunk-level insertion sort that starts that process, and a run is a property of the input is the reason a sort that reads its runs first does not have to.

So the answer to the question the earlier essay posed, where a stable sort with a small buffer does the most work no algorithm needs, has two parts. Measured as a multiple of the floor, the worst is random keys at a small buffer, 85 times. But there the floor is a weak bound, since nothing that sorts by comparing and merging approaches it. Measured against what the input allowed a merge sort to save, the worst is the library on nearly sorted input, 130 times the floor where a sort that reads its runs and trims its merges is 1.5.

What the floor does and does not promise #

A floor of one move a key on a random file is reachable, but not by a merge sort. A sort that may keep a separate array of positions can compare and sort the positions, leaving the keys alone, then move each key once by following the cycles, and pay exactly the floor in moves of keys. Its extra memory is a position for every key, the thing a buffer-limited sort exists to avoid. Stable sorts that reach a constant number of moves a key in place have been described in the research literature, with methods no standard library carries. A guarantee that depends on an allocation measured what the library’s merge sort spends when it gets less buffer than it asks for, and moves were where it paid.

On the inputs a merge sort can exploit, the floor is close. On batches, a trimmed merge is within half the floor of it, and the half is the buffer’s copy, which the floor does not charge because it imagines the sort already knows where everything goes. Counting instead of timing is why every number here is a move. A move of a 16-byte record and a move of a 4-kilobyte one are the same unit on these plates and not on a machine.

Where the measurement stops #

One draw of each input. Every input is built once from a stated seed, at 65,536 keys. The batch factors, 1.40 to 1.49, vary smoothly with the overlap, which suggests the single draw is not doing the work.

Distinct keys. With equal keys a stable sort’s final positions are still determined, by rank and then by position, and the floor is computed the same way; the inputs here simply have none.

Moves of keys, not of positions. The floor counts writes of keys and nothing else. A sort that moves indices or pointers instead would be charged differently, and the cycle-following sort above is cheap only because its index moves are not counted.

Still open: a late tail sorted in the buffer before it is merged #

The late tenth costs its sort two thirds of its moves in sorting itself, a dozen levels of merging over 6,554 keys. Those keys arrive together at the end of the file, and at a 64th buffer the buffer holds 1,024 of them. A sort that read its runs first, as a request that reads the input first did for its buffer, would see one long sorted run and a short unsorted tail, and could sort the tail by a different method than merging. It could insert each late key into a sorted run kept in the buffer, then merge the buffered run into the head, and do so a buffer at a time.

The measurement that follows gives the sort that rule for any final stretch shorter than a tenth of the file and counts moves at every buffer on the late and random tails. The prediction is that sorting by insertion into the buffer costs about half a buffer’s length in moves for each key, far more than the dozen levels at a 64th, so the rule only pays when the buffer is small. There, merging the tail in buffer-sized sorted pieces replaces most of the tail’s own sort with merges into the head, and the late tenth should fall from 2.93 moves a key to under two. It could fail on the merges into the head. Six sorted pieces of a thousand keys merged into the head one at a time each cross the head’s top fifth, and six such merges may cost more than the tail’s own sort saved.