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.