The skip the split already made

The buffer a schedule cannot bend gave a stable merge sort a buffer fixed in advance, a sixteenth or a sixty-fourth of the input, and asked it to choose a merge schedule that fits. No schedule could. On inputs of comparable runs every schedule ends with a merge of two large pieces, and a merge whose shorter side does not fit the buffer is split the way libstdc++'s std::stable_sort splits it: halve the longer run, find the matching point in the other by binary search, rotate the piece between, and merge the two halves separately. Every extra move a small buffer caused was a rotation, six to eight and a half a key at a sixteenth.

Its closing section noticed that the rotation treats the two runs as arbitrary. A sort that has read its runs knows more. It could find, before splitting, how much of each side is already in place against the other — the left run’s keys that are no greater than the right run’s first key, and the right run’s keys that are no less than the left run’s last — and leave them out. Timsort opens every merge this way, and when galloping pays measured the exponential search it uses. The section predicted that on runs of random values, which interleave everywhere, this would save almost nothing, and that on runs overlapping only at their ends it would remove most of the rotation cost. It named the number that would decide: the share of each split merge that galloping can set aside.

The sort, the trim and two new inputs #

The sort is the earlier page’s to the move, and the one a request that reads the input first built. It finds the input’s natural runs in one pass, extends runs shorter than eight keys by binary insertion, and merges the adjacent pair with the shortest shorter side first. A merge whose shorter side fits the buffer copies that side into the buffer and merges back into place, as std::__merge_adaptive does. One that does not fit is split by std::__merge_adaptive_resize. Moves and comparisons are counted, and every result is checked sorted and stable.

The trim is one step before each merge. An exponential search from the left end of the left run finds the first key greater than the right run’s first key, and one from the right end of the right run finds the first key not less than the left run’s last. Equal keys stay on their own side, so stability holds. Only the keys between the two positions are merged. The trim is measured in two strengths. It is applied once before each scheduled merge, or before every split as well, inside the rotation’s recursion. The two differ in the second place at most, and the second is the one reported.

The earlier page’s inputs are four and sixteen runs of random values, a sorted file with a random tenth appended, and random keys. None of them has runs that meet only at their ends. Two inputs are added that do. Sixteen batches: each batch sorted, its keys spread over a range that overlaps the next batch’s by a stated share, like records written in batches by time where a few late ones land in the next batch. It is also roughly what runs twice as long as memory found replacement selection producing on nearly sorted input: long runs whose key ranges meet at their ends. A late tenth: a sorted file with a tenth of its keys appended in random order, drawn not from the whole range but from its top fifth, like late arrivals. Everything is at 65,536 keys.

Two thirds set aside, half a per cent saved #

On the sorted file with a late tenth, at a sixty-fourth of buffer, the trim sets aside 67% of the keys in the merges too large for the buffer, and the sort’s moves fall from 2.95 a key to 2.93. The number the prediction said would decide came out large, and it decided nothing. Two thirds of the split merges’ keys were found to be in place, and leaving them out saved half a per cent.

The prediction was right about runs of random values. On four and sixteen of them the trim sets aside nothing, and saves nothing, as the section expected. Their values interleave from the first key to the last, so the left run’s first key is already greater than something in the right run and the gallop stops at once. The same holds for random keys and for the random tenth, where the tail’s keys span the whole range.

The other side of the prediction fails, and the reason is not in the trim. It is in the split the trim was meant to improve.

Halving finds the same keys, and moves nothing to find them #

The library’s split halves the longer run and binary-searches the other, and when a stretch is in place that search finds it and the rotation between has nothing to move. On the last merge of the late tenth — a sorted head of 58,982 keys against the tail of 6,554, merged into one run — the head is the longer side. Halving it puts the cut at the key in the middle of the head, 45% of the way up the key range. The binary search for that key in the tail finds that every tail key is larger, so the piece to rotate is empty. The first half of the head is then merged against nothing and returns at once. The second half repeats the step.

After three such steps 21% of the file is still in play, the head’s top stretch and the tail, and not one key has moved. The trim reaches 20% in one step, by galloping. From there the two do the same work and move the same keys: 1.04 moves a key for the whole merge either way. Bisection costs a few binary searches, about fifty comparisons on a merge of 65,536 keys, and the gallop costs about as many. What the trim sets aside, the split had already set aside, level by level, without moving it.

So the trim’s large set-aside share is real and measures nothing the split did not already know. A rotation of an empty range moves no keys. The prediction assumed that because the split does not look for in-place stretches, it pays for them. It does not look, but it finds them, because halving and binary search are enough to discover that half of a run is below everything in the other.

The one place halving and trimming differ is where a halving cut lands inside the overlap rather than below it. With the late keys drawn from the top 40% of the range, the first cut, at 45%, still falls below the overlap and moves nothing. The second falls at about 70%, inside it, and that rotation moves part of the head’s upper stretch past the tail’s lower keys: 49,230 moves at the second level alone. The trim cuts where the overlap begins, and the halving that follows falls in the middle of the part that interleaves. The whole merge costs 2.45 moves a key halving and 1.95 trimmed. The trim’s gain here is not the keys it skips. It is that the cut positions are chosen inside the part that has to move.

Where the late keys reach #

Across the reach of the late keys, the trim saves nothing at a tenth, a fifth or the whole range, and 12% at 40% and 16% at 70%. At a tenth and a fifth the halving cuts fall below the overlap for the first few levels and find the in-place stretch for free. At the whole range the tail interleaves with everything and there is nothing in place. In between, a halving cut lands inside the overlap, and a rotation that the trim avoids is paid.

The saving depends on where the successive middles of the head fall against the overlap, which is a property of the geometry and not of how much is in place. Nothing about the input’s share of in-place keys predicts it: the late fifth has more of its split merges in place than the late 40%, and it is the late 40% where the trim saves. The library, which reads no runs, moves 12.4 to 17.6 keys a key on the same inputs, three to six times as many, and the difference between it and either version of the run-reading sort is much larger than anything the trim changes.

The merge that fits is the one that wastes #

On sixteen batches overlapping by 5%, the untrimmed sort moves 3.54 keys a key with a quarter of the input as buffer and 0.16 with a 256th: the larger the buffer, the more it moves. At a sixteenth each batch is 4,096 keys, a sixteenth of the input, so every merge of two batches fits the buffer. A merge that fits copies its whole shorter side into the buffer and merges it back, two moves for every key of that side and one for every key of the other side that has to shift. It does this even though 95% of each batch is already in place against its neighbour. At a sixty-fourth no merge of batches fits, so every merge is split, and the split finds the in-place stretches by halving and moves almost nothing. The paradox is exact: the buffer’s size decides whether a merge is copied or bisected, and on nearly sorted input bisection is the cheaper of the two.

Trimmed, the sort moves 0.13 keys a key at every buffer from a quarter down to a 256th. The trim sets aside the 95% of each merge that is in place, and what is left, the overlap between two batches, fits the buffer at every size measured. It is copied and merged, the only work there is to do. The buffer stops mattering because the merges it would have decided about are no longer large. Only at a 1,024th, 64 keys, does an overlap of about two hundred keys stop fitting, and both versions rise to about 0.3.

This is where the trim earns its place, and it is not where the section looked for it. The rotation did not need the trim, because bisection is already a way of skipping what is in place. The buffered merge needs it, because a buffered merge copies before it compares. std::__merge_adaptive moves the shorter side into the buffer with no look at whether any of it is already where it belongs, and a sort that has read its runs pays for that on exactly the inputs where reading the runs should have paid best. A guarantee that depends on an allocation found the library’s buffer changing which count it spends. Here, without a trim, it changes the count in the wrong direction. The request no price of memory would make priced buffers against the moves they save and found every size but the library’s own worth choosing at some price; on the batches, untrimmed, no price of memory makes a larger buffer worth anything, because it buys more moves.

How much overlap the trim can use #

Trimmed, the moves grow with the overlap, from 0.03 a key at 1% to 1.40 when each batch’s range covers the whole of the next’s; untrimmed at a sixteenth they start at 1.88 and rise only to 2.34. The trimmed sort pays for what interleaves and nothing else. The untrimmed sort at a sixteenth pays for every key of every shorter side, overlap or not, so its cost is nearly flat until the overlap is large enough to add rotation on top.

At a sixty-fourth the untrimmed sort is already bisecting, and the trim’s advantage is smaller: 0.51 against 0.13 at 5%. At half a batch of overlap the trim loses, 1.39 moves a key against 1.32. The reason is the one the late tail showed from the other side. Trimming moves the middle of the merge that the split then halves, and on this input the cut after trimming lands where the rotation is a little larger than the one the untrimmed halving happened to make. The difference is 5%, and it comes from where two binary searches land, which neither version controls.

What the trim costs where nothing is in place #

Where nothing is in place, the trim costs comparisons and saves almost no moves: on random keys at a sixteenth it adds 0.28 comparisons a key and saves 0.20 moves. On random keys the sort’s runs are the eight-key runs its insertion step builds, so it makes thousands of short merges, and every one of them opens with two gallops that stop after a comparison or two. That is the cost. It is under 2% of the 16.0 comparisons a key the sort makes. On runs of random values there are only a handful of merges, and the trim adds under a hundredth of a comparison a key.

On the batches the trim removes comparisons as well as moves. A buffered merge compares its way through the in-place stretch key by key, since it copies first and only then merges. Setting that stretch aside by galloping costs a dozen comparisons a merge and saves thousands. When galloping pays found Timsort’s galloping mode costing six comparisons on random input and saving tens of thousands on nearly sorted input. The trim is that bargain in its simplest form, taken once at each end of each merge rather than switched on and off inside it.

The cost is small enough that a sort which reads its runs has no reason not to trim. What it should not do is expect the trim to rescue its rotations. A run is a property of the input argued that “nearly sorted” is a recipe, not a measurement, and this page adds a caution on the same lines. A share of keys in place is a measurement, and it can be large while telling nothing about the cost of a split.

What the measurements leave out #

Moves and comparisons, not time. As on every page here, the counts are exact and machine-independent, which counting instead of timing explains. A buffered copy moves keys in a sequential sweep and a rotation in cycles, and a timer could weigh them differently.

One size, one draw an input. Every input is 65,536 keys from one seed. The batches’ overlap is uniform: every boundary overlaps by the same share. Real batches would vary, and the trim’s saving would follow the mix.

The trim is taken only at the ends. The gallop sets aside each merge’s in-place prefix and suffix. It does not find in-place stretches in the middle of an interleaved region, which Timsort’s galloping mode does as it merges. On the batches the interleaved region is random and there are none to find. On inputs where runs interleave in long blocks there would be.

The late tail’s reach is one shape. Late keys drawn uniformly from the top share of the range are one model of lateness. Keys late by a bounded amount of time, each one close to where it belongs, would give a tail that interleaves with the head only near its top, and the trim would behave as it does at a reach of a tenth.

Still open: the moves a stable merge cannot avoid #

Trimmed, the sort moves 0.13 keys a key on batches overlapping by 5%, at every buffer. That is the cost of the overlap alone, and the question is how close it is to the least any stable merge could manage. A key whose final position differs from where it starts must move at least once. The trimmed sort moves the keys of each overlap’s shorter side twice, into the buffer and back, and the other side’s overlapping keys once. That suggests the floor should be about two-thirds of the trimmed sort’s count, and that the gap is the buffer’s copy.

The floor a merge cannot reach solved the comparison game for a merge and found the counting floor unreachable. Moves have a simpler floor. The measurement that follows counts, for each input, the keys not already in their final position, which is a lower bound on the moves of any sort, and sets the trimmed sort, the untrimmed one and the library against it at every buffer. The prediction is that the trimmed sort stays within a factor of two of the floor on batches and on late tails at every buffer. On runs of random values it should be several times the floor, because there nearly every key is out of place, but a rotation moves each key several times over. Where the factor is largest is where a stable sort with a small buffer is doing the most work that no algorithm needs. That is the number a library would want before deciding whether a smarter split is worth writing, now that a trim has been shown not to be one.