A request that reads the input first

The request no price of memory would make priced libstdc++'s std::stable_sort at every buffer from nothing to the whole input, in element moves against the memory held. Every buffer size was the cheapest at some price of memory, except the one the library asks for. Its request of half the input lay above the line between a quarter and the whole at every size measured. Every buffer on that page was requested before the sort had looked at a single key.

Its closing section pointed at sorts that look first. When galloping pays and the pattern that defeats the pattern found that sorts which inspect the input before committing can spend far less on presorted data. A merge of two runs that are already long needs a buffer only as large as the shorter of them, and the longest merge a natural merge sort performs is often far smaller than half the input. The section proposed one linear pass to find the natural runs, and a request the size of the largest merge the resulting schedule would perform. It was to be compared with the fixed requests of a quarter, a half and the whole, on random input and on inputs of a few long runs. It predicted that on random input the pass would cost a little and save nothing. On a few long runs the request should fall to the size of the second-longest run, with moves no higher than the half-buffer sort’s.

The prediction about moves is right, by a wide margin. The prediction about the request is wrong, and the reason is in the schedule, not the input.

A sort that reads before it asks #

The sort measured here makes one pass over the input to find its maximal non-decreasing runs. It uses non-decreasing runs only, since reversing a descending run could reorder equal keys, and a stable sort may not. Runs shorter than 32 keys are extended to 32 by binary insertion, as Timsort extends them. Adjacent runs are then merged in balanced rounds, and each merge copies its shorter run into the buffer and merges from that run’s end, so no merge needs more than its shorter run. The request is the largest shorter run in the whole schedule, and it is known after the pass, before any merge is made. Moves and comparisons are counted as on the earlier page: every element assignment is a move, and the pass is charged its comparisons.

The inputs are 65,536 keys made of $k$ ascending runs of random lengths, from one run (sorted) to 4,096, and random keys. A run is a property of the input found a count of natural runs a better description of presortedness than any recipe for making presorted data, and the pass here finds almost exactly the runs each input was built from: 1,016 of 1,024, 3,899 of 4,096.

On four long runs the run-aware sort makes 2.80 moves a key against the library’s 17.2; on sixteen, 5.52 against 17.2; on a sorted file, none against 16.7. The library’s structure does not look at the input. Its half-sized buffer sorts each half with a merge sort that works through insertion-sorted chunks of seven and merge passes that copy between the array and the buffer, whatever order the keys arrived in. Its moves barely move with the input, from 16.7 a key on sorted input to 18.7 on random. The run-aware sort’s moves grow with the logarithm of the number of runs, because each round of merges moves about the whole file once. On a few long runs that is a few rounds, where the library always makes about thirteen passes, one for each doubling from its chunks of seven to the whole file.

The saving holds up to 1,024 runs, where the run-aware sort’s 16.8 moves a key is level with the library’s 17.3, and it is lost by 4,096 runs, 21.4 against 17.6. On random keys the run-aware sort makes 24.9 moves a key against 18.7. The prediction said the pass would save nothing there. It does worse than nothing. Random keys have runs about two keys long, so the run-aware sort extends them to 32 by binary insertion, and that insertion costs 8.5 moves a key, against 3.2 for the library’s insertion sort in chunks of seven. Its merges then cost 16.4 moves a key over eleven rounds, against the library’s 15.5 over thirteen. Of the 6.2 extra moves a key, 5.3 are the insertion. The price on random keys is the minimum run length, not the pass.

The minimum run is a constant somebody chose #

Thirty-two is Timsort’s own minimum run, and the run-aware sort borrowed it. The threshold somebody chose went looking for where such constants come from in library sorts and found them reasonable and underived. This one can be priced directly, since it is the source of the run-aware sort’s loss on random keys.

On random keys, a minimum run of eight takes the run-aware sort from 24.9 moves a key to 21.3, and a minimum of four gives the same 21.3. It is still worse than the library’s 18.7. On input of 4,096 runs a minimum of eight gives 17.3 moves a key against 21.4 at thirty-two, now below the library’s 17.6. On 1,024 runs it gives 14.2 against 16.8, and on sixteen runs the minimum makes no difference, since every run is already far longer than any minimum. With a minimum run of eight, the run-aware sort makes fewer moves than the library on every input made of runs, and more only on random keys. The comparisons move the other way, but slightly: 15.8 a key on random keys at a minimum of eight against 15.7 at thirty-two.

So the prediction for random input, that the pass costs a little and saves nothing, is right once the minimum run is chosen for moves rather than borrowed. The pass costs one comparison a key. The loss that remains, 2.6 moves a key, was not traced further. The sort the library ships found Python, Java, Rust and Android sorting objects with Timsort, which finds runs before it merges, and C++ shipping a stable sort that does not look. The measurements here say what looking would be worth to C++'s: nothing on random keys, and most of its moves on anything else.

The buffer barely falls #

On every input from two runs to 4,096, the run-aware sort asks for between 36% and 45% of the input, against the library’s half. The prediction said the request would fall to the second-longest run, and on two runs it does exactly that: the shorter of two runs of random length is 45% of this input. But it falls no further as the runs multiply. On sixteen runs the longest single run is a small fraction of the file, and the request is still 43%.

The schedule shows why. A balanced schedule merges runs in pairs, then pairs of pairs, and its last merge joins two halves of the file. The shorter side of that last merge is at most half the input, and for runs of similar lengths it is close to half, since each half holds about the same number of keys. On eight runs the first round needs at most 640 keys of buffer, but the last needs 1,776, 43% of the input. What the pass learns about the runs sets the bottom rounds’ buffers. The top round’s buffer is set by the schedule. For a balanced schedule, that is roughly half the input on almost any input.

So knowing the runs buys moves, not memory. A request sized from the runs is a smaller request than the library’s only by the difference between 43% and 50%, and it saves that difference only by looking.

Where the request does fall #

The request falls when the last merge is lopsided, which happens when one run dominates the file. The most common input with that shape is a file that was sorted once and has had new keys appended since: a log, an index rebuilt periodically, a table sorted by date with a day’s new rows at the end.

With a tenth of the file appended in random order, the run-aware sort asks for 3.7% of the input and makes 9.1 moves a key; the library asks for half and makes 16.9. With a thousandth appended it asks for 0.05% and makes 1.9 moves a key. The request is at most half the appended share at every size of tail. The sorted part is one long run, and every merge that includes it has the tail’s pieces as its shorter side. At the top of the schedule the shorter side is the part of the tail that fell on one side of the final split, not a half of the file. Here the prediction is right in the form it was meant: the request falls to the size of what is not already in order.

The moves fall less than the request does. Even with a thousandth appended the run-aware sort makes 1.86 moves a key. Each new key lands somewhere inside the long sorted run, and a merge must move every key of the long run that lies beyond the first new key. The balanced schedule makes the long run take part in merges at every level. A schedule that merged the whole tail first and the long run once at the end would move the long run once. Timsort’s rule of merging runs whose lengths do not shrink fast enough approaches that schedule on this kind of input; a balanced schedule does not.

What the pass costs #

The pass is one comparison a key, and on sorted input it is the entire sort: 1.00 comparisons a key against the library’s 9.00, since a merge sort that does not look first still compares every chunk. With its merges included, the run-aware sort makes fewer comparisons than the library on every input measured, including random keys, 15.7 against 15.8. On random keys its insertion compares more, 3.7 a key against the library’s 2.4, but its merges compare less, 11.0 against 13.5, because they make eleven rounds where the library makes thirteen, and that pays for the pass and the insertion together. So the pass is never a cost in comparisons. On random keys the run-aware sort’s disadvantage is all in moves, from the insertion that extends short runs, and that is the price of the minimum run length rather than of looking.

A request made as the merges need it #

A sort that has read its runs can do better than ask once. CPython’s list sort, a Timsort, keeps a temporary array that it grows when a merge needs more room than it has, and it never merges through more than the shorter of two runs. Its buffer is therefore at most the largest shorter run its own schedule meets, which is the quantity this page calls the request, reached lazily instead of requested up front. The difference matters under memory pressure. A request made up front either succeeds or falls back to a smaller buffer for the whole sort, which is what the earlier page priced. A buffer grown on demand is small for as long as the merges are small, and only the last merges of a sort need the large one.

The measurements here say how large that last need is. With a balanced schedule, on anything but a file that is mostly one run, it is 36 to 45% of the input, close to the library’s half. A lazily grown buffer does not change that peak. It changes only how long the sort holds memory it does not yet need, and on a sorted file with a small tail the peak is small anyway. Neither way of asking escapes the schedule’s last merge. Only a different schedule does, which is where this page ends.

Where these numbers stop applying #

One schedule. Every merge here is in balanced rounds. Timsort merges runs as they are found, holding a stack whose run lengths must shrink geometrically, and a schedule like that merges short runs together before they meet a long one. It could lower the request on inputs of many similar runs only by merging unevenly. That costs moves, and the trade was not measured.

Distinct keys. The inputs have no repeated keys. With many equal keys the non-decreasing runs would be longer, since equal neighbours extend a run, and every number here would fall. A descending run of distinct keys could also be reversed in place, as Timsort reverses strictly descending runs; that would make a reversed file one run, where the sort here would find 65,536 runs of one key each. The order equal keys keep set out why a stable sort may reverse only strictly descending runs, and the run-aware sort here reverses none.

No galloping. Every merge takes one key at a time. When galloping pays found that searching for how many keys to take at once saves many comparisons on presorted input and costs almost nothing on random input. It would lower the comparisons here by an amount not measured, likely most on the tail inputs, where one side of a merge wins long streaks. It would not lower the moves, since every key a merge passes over still has to be written.

One draw of run lengths. Each input of $k$ runs is one draw of random run lengths, and the request depends on where the last merge’s split falls among them. Another draw of two runs could give a shorter run of a tenth of the input or of nearly half. The request’s range, 36 to 45% across these inputs, is a range over draws as much as over $k$.

Moves as the earlier page counted them. A move is an element assignment of one record. A guarantee that depends on an allocation found that the standard’s comparison bound says nothing about moves. The earlier page found that the record’s size scales moves and memory alike, so the comparison between designs does not depend on it.

The request, not the allocation. Knowing the request after the pass lets a sort ask for exactly what it needs, and what an allocator does with a request of 3.7% of the input rather than 50% — whether it succeeds more often under pressure — was not measured.

Still open: a schedule chosen for its buffer #

The request stayed near half because a balanced schedule’s last merge joins two halves of the file. The schedule is a choice, and the pass that finds the runs knows enough to make another. Merging the runs in an order chosen to keep every merge’s shorter side under a stated size — always merging the two shortest adjacent runs, say, until the remaining runs are all longer than the buffer — would trade moves for memory at a rate the run lengths determine.

The measurement that follows sets a buffer before sorting, a quarter, an eighth, a sixteenth of the input, and chooses a schedule whose every merge fits, using rotation for any merge that cannot. It measures the moves each buffer costs on inputs of few and many runs. The prediction is that on a few long runs a buffer of a sixteenth costs little: the long runs can be merged last, each against short neighbours, and only the final merges need more than the buffer holds. On random keys it should cost what the earlier page found for the library at a sixteenth, since short runs give a schedule nothing to choose between. The question is whether a sort that reads its input first can do more than size its request honestly — whether it can bend the schedule so that the memory it needs is set by the input’s disorder rather than the input’s length.