Practice — the series
-
The sort the library ships
Every sorting algorithm measured in these essays so far has one thing in common — none of them is what runs when a program calls sort. Python, Java, Rust and Android run Timsort; C++ runs introsort; Java's primitive sort is dual-pivot quicksort. Not one of the four was in this collection, and the reason it matters is that they are not algorithms in the sense the other essays use the word.
-
A run is a property of the input
A benchmark that says "nearly sorted" never says how nearly. It is a recipe with a seed, not a measurement, and an adaptive bound stated against it is a bound with an undefined second parameter. Counting the natural runs turns the shape of an input into a number — and then Timsort's bound becomes something that can be fitted rather than quoted.
-
When galloping pays
Timsort's merge does not always take elements one at a time. When one run has won seven times in a row it switches to searching for how many to take at once, and switches back when that stops paying. The mode saves 22,104 comparisons on nearly sorted input, 33,270 on input with few distinct values, and costs exactly six on random input — which is the whole design in three numbers.
-
The pattern that defeats the pattern
Quicksort's bad cases are patterns — sorted input, organ-pipe input, an adversary's construction. Introsort's answer is to notice the damage and switch algorithms. pdqsort's answer is to notice the pattern and break it, deterministically, with four swaps. On input with eight distinct values that turns a quadratic disaster into a linear sort, and the whole difference is one extra partition scheme.
-
A guarantee that depends on an allocation
The C++ standard promises std::stable_sort N log₂ N comparisons if enough extra memory is available, and N (log₂ N)² otherwise. On 65,536 keys the library's own structure, denied its buffer entirely, makes 1,366,510 comparisons — a third more than with it, and twelve times under what the standard allows. What it spends instead is moves: 10.4 million against 1.2 million, 94% of them rotations. The standard bounds the count that barely changes and says nothing about the one that grows as n log² n.
-
The request no price of memory would make
libstdc++'s stable_sort asks for a buffer of half the input. Priced in element moves against the memory held, every buffer from nothing to a buffer as large as the input has a range of memory prices at which it is the cheapest — except that one. A quarter of the input costs 1.4% more moves; a full buffer, merging out of place, saves 8% more for twice the memory; and the half-sized request sits above the line between them at every size measured. The record size, predicted to move the answer, does not: moves and memory both cost in proportion to it.
-
A request that reads the input first
A stable sort that asks for its buffer before it has looked at the input asks for half of it, whatever the input is. One pass to find the input's natural runs lets a merge ask only for the shorter run of each merge it will make. On input of four long runs that takes the moves from 17 a key to under 3, and on a sorted file it makes no moves at all. The buffer it needs barely falls: on anything from two runs to four thousand it asks for 36 to 45% of the input, because a balanced schedule's last merge joins two halves of the file. The request falls only where one run dominates. On a sorted file with a tenth of it appended at random, it asks for 3.7% of the input.
-
The buffer a schedule cannot bend
A stable merge sort that reads its input's runs first needed 36% to 45% of the input as buffer, because a balanced schedule's last merge joins two halves of the file. The repair proposed was to set the buffer first and choose a schedule whose merges fit it. No schedule can: merging the smallest pieces first still ends with two large pieces on almost every input, and every merge that does not fit is split by rotation. The extra moves are all rotations, six to eight and a half a key at a sixteenth of the input on every input, so the two costs simply add. Reading the runs still beats the library at every buffer on every input made of runs, and the schedule matters only where one run is most of the file.
-
The skip the split already made
A stable merge with too small a buffer is split by rotation, and the rotation was proposed to be the waste: gallop from each end of a merge first, set aside what is already in place, and rotate only the rest. On a sorted file with late arrivals the gallop sets aside two thirds of the keys in its split merges and saves half a per cent of the moves, because the library's split — halve one run, binary-search the other — had already found those stretches by bisection and moved nothing there. Where the gallop pays is the merge that fits the buffer, which copies its whole shorter run out and back: on sixteen overlapping batches it takes the sort from 1.92 moves a key to 0.13, and makes a larger buffer stop costing more.
-
The moves no stable sort can skip
Any sort must move every key that starts out of place, and with one spare cell it must spend one more move on each cycle of the permutation. Against that floor, a stable merge sort trimmed to the keys not already in place moves 1.46 times the least possible on records written in overlapping batches — the two thirds the prediction named, and for its reason. On a sorted file with a late tenth appended it was predicted within twice the floor and moves 15 times it, because the late tenth arrives in random order and sorting it among itself is two thirds of the work.
-
Pieces that fit the buffer
A sorted file with a late tenth appended costs the buffer-limited stable merge sort 2.93 moves a key at a buffer of a 64th, fifteen times the least any sort could move, and two thirds of it is the tail sorting itself. Taking the tail a buffer at a time, inserting each key into a sorted piece in the buffer and merging the piece into the head, was predicted to bring that under two moves a key at small buffers. It never comes within twice the merge sort: insertion costs a quarter of a piece a key, and the smaller the pieces the more often each one's merge crosses the head's top fifth. The same pieces sorted in place by merging do pay, at 2.41 moves a key, and for a reason the proposal did not name: a piece that fits the buffer merges into the head without a single rotation. The gain lasts only while the tail belongs near the top of the file.
-
How many pieces the head can afford
A sorted file of 65,536 keys with a late tenth appended in random order can be sorted by taking the tail a buffer at a time, sorting each piece, and merging each into the head. It beats the buffered merge sort at a 64th of the file and loses at smaller buffers, because every piece's merge crosses the head's top keys again. Merging the pieces with each other first, while a round costs less than the crossings it removes, was predicted to win at every buffer. It wins at none. The first round always costs more than no rounds — 18.97 moves a key against 16.04 at a 1,024th — because a group larger than the buffer crosses the head by rotation, and the cost falls under the merge sort's only when the rounds run all the way, which is the merge sort. The head can afford thirteen pieces and not twenty-six; beyond that the best a tail can do is be one run.
-
The rotation that could be priced
A sort that finds a sorted file with a late tail can send the tail's pieces straight into the head or merge them to one group first, and a rule that priced both ends as shifts chose wrongly at a buffer of a 128th, because a group longer than the buffer crosses the head by rotation. Priced instead from measurements of the library merge on synthetic runs, the long crossing comes within 3% of what the sort pays at every buffer and the choice at a 128th comes right. But the rule prices the pieces against the head as it stood before any of them joined it, and each piece also crosses the pieces before it: priced up to 37% low, they send the sort to the dearer end at a 256th.
-
The head each piece will meet
A rule that priced a sorted file's late tail two ways before moving anything chose the dearer end at a buffer of a 256th, because it priced every piece against the head as it stood before any piece joined it. Each piece also crosses the pieces before it, and those are known in advance: one binary search of each earlier, already sorted piece counts them. Priced against the head each piece will meet, the pieces come within 6% of what they cost at every buffer, and the rule chooses the cheaper end at all seven buffers and all ten reaches of the tail. A third of what each piece crosses turns out to be other pieces, as the arithmetic of the band says it must.
-
Every number of rounds, priced
A library merge sort given a file whose last tenth arrived late sorts the tail a buffer's worth at a time and then either sends every sorted piece into the head or merges the pieces first. A rule priced from measured tables chose the cheaper of the two ends at every buffer. Priced the same way at every number of rounds in between, it was predicted never to choose a partway number and to price every one within 6%. It chooses the cheapest number of rounds at all seven buffers on that input and at 14 of 15 settings across reaches and buffers; the one partway optimum among them — six rounds of seven, by 1% — it misses by choosing five, 3.8% dear. But the estimates are not all within 6%. At the three smallest buffers the first round is priced 15% to 25% wrong, high at one buffer and low at the others, because its pairs of pieces cross the head in a way no table of single runs describes; the rule survives it because one round is never close to the cheapest.