Natural run — where it appears
Named by 13 essays across 2 fields — each of them below, with the objects they name alongside it.
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.
A run answers what nobody asked
Bidirectional selection sort remembers its past comparisons in two chains, and on sorted or reversed keys the chains need a link for every key. Keeping instead what is known about adjacent positions — which of each neighbouring pair is larger, forgotten when a swap moves either — turns a monotone stretch into a single run with a direction. On reversed keys one run replaces 1,025 links. On sorted keys the run does more than remember: it answers 260,610 questions the sort had never asked, from two keys' positions alone, and the sort makes 2,045 comparisons at 1,024 keys where the chains leave 263,167. On organ-pipe keys it cuts a quarter of the comparisons; on random keys, nothing.
A pass repaid by the scans after it
Give the two-ended selection sort one pass between neighbours before it starts, n − 1 comparisons, and sorted and reversed keys cost exactly that pass. The pass was predicted to be repaid in the first scan, and almost none of it is. On organ-pipe keys it saves 43,776 comparisons at 1,024 keys, 97% of them in the scans after the first. On random keys it costs 236, not 1,023, because later scans use the short runs it found. It breaks even on runs of four keys at every size — and the sort stays quadratic on every input that is not one run.
The runs too short to drop
A pass between neighbours leaves the two-ended selection sort a record of 674 runs on 1,024 random keys, and the scans after it use them to repay three quarters of the pass. Keeping only runs of three keys or more was predicted to cut the record by two thirds and give back under a tenth of what it repaid. It cuts the record by 63%, and gives back 69%: runs of two keys answer half of everything the record answers, because three quarters of its answers are about two neighbouring positions — the question a scan asks about the key beside the extreme it has just found. The record's cost was never in its short runs. It was in writing each run as three words: every neighbouring pair at two bits a pair is 64 words, a thirty-second of the run list, and keeps all of them.
What it costs to consult two bits a pair
The two-ended selection sort's record of adjacent order can be kept as two bits a neighbouring pair or as a list of runs, and the page that compared them counted both as free to read. Priced, the bits read 1.09 words a question on 1,024 random keys — under the two predicted — and a binary search of the run list takes 8.8 steps, because the pass leaves 503 runs to search. The run list was predicted to win from runs of sixteen keys; it wins only from runs of 512. Both prices are small and neither is small enough. Asked every question the sort makes, the bits spend 201 word reads for every comparison the record saves on runs of four keys, 764 at 4,096 keys, where a table of compared pairs broke even at three. The record repays its reading only on long runs, and the pass that finds them is also the cheapest place to decide whether to consult at all.
A filter that reads the word it saves
A selection sort's record of adjacent order, two bits a neighbouring pair, costs 1.09 word reads a question and spends 201 of them for every comparison it saves on 1,024 keys in short runs, because it is asked everything and answers almost nothing. A filter bit beside each pair, set only where a run could start, was predicted to turn away three quarters of the questions and cut that price to under sixty. It turns away two thirds and cuts the price to 185. The questions it turns away were already refused in the first word, the filter is read in that same word, and one read a question is a floor no filter can go under.
A run end kept in a register
A selection sort's record of adjacent order spends about a word read on every question it is asked, and on short runs it is asked 184 questions for every comparison it saves, so no filter read in that word can make it pay. Every question starts from one of the sort's two current extremes, and what the record can say about all of them is one number: where the run from that extreme ends. Kept in a register beside each extreme and refreshed only when it changes, that number cuts the reading to a forty-fifth on 1,024 keys in runs of four, and the price of a saved comparison from 201 word reads to 4.5, where it stops growing with the input.
A register dropped by what it already knew
Two registers beside a two-ended selection sort's extremes cut the reading of its record of adjacent order to a forty-fifth on short runs, and made it worse than reading the record plainly on long ones: 53.5 words a question on a sorted array of 1,024 keys against 22.1. The swaps were blamed, and the proposed repair kept the part of a broken run beyond the break as a register of its own. It changes the reading by under 1% anywhere. On the sorted array the survivors are kept 523,775 times and asked 1,022 times, and the sort makes no swap at all: every one of the 263,167 relearning drops there is a pair the record already held, rewritten at the same value by a neighbour's question that the previous scan's chains answered. The swap never broke the register. Learning what it already knew did.
A register kept through a confirmation
Two registers beside a two-ended selection sort's extremes, holding where the run of known order from each one ends, read 53.5 words a question on a sorted array of 1,024 keys, more than reading the record plainly — because 263,167 times a neighbour's question, answered by the previous scan's chains, rewrote a pair at the value it already held, and each rewrite dropped a register. Kept through such a confirmation and dropped only when a pair is forgotten or turns round, the registers read 0.347 words a question on that array, a 154th, and 0.345 on 4,096 keys: the reading stops growing with n. They become the cheapest record at every run length, 49 to 73 times under the next on runs and 5.75 times under the run list's search on the sorted array, and the price of a saved comparison now falls as runs lengthen, from 3.97 word reads at runs of four to 0.35. The dearest saving is now the short run's, and it is still above the 3.1 at which a table of compared pairs breaks even.
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.
Named alongside it
The objects these essays reach for when they reach for this one.
Comparison countSpace time tradePredictionSelection sortBit vectorLibrary sortHonest limitStabilityAdaptive sortData movementMerge sortTransitivity