A switch that reads the long runs
The two-ended selection sort finds the smallest and largest of its unsorted part on every scan, and a run of essays has taught it to remember. Its record holds two bits for each neighbouring pair — unknown, or known in one direction — which a run answers what nobody asked introduced, and a question whose keys lie at the two ends of a stretch of pairs pointing one way can be answered from the record instead of by comparing. What it costs to consult two bits a pair priced reading it, and a run end kept in a register and a register dropped by what it already knew made the reading short. A register kept through a confirmation made consulting the record cheap, a few register words a question. What it saves is comparisons, and on long runs it saves many; on short runs it saves too few to pay for the reading.
A record switched off by its runs let the sort decide. The pass between neighbours, which the sort makes before its first scan, counts the runs, and a switch kept the record only when the mean run, over the runs, reached a threshold. Comparisons and word reads were charged together at an exchange rate , word reads a comparison is worth. On even runs at the best threshold was a mean of six, as predicted, and what it saved there was three thousandths of a sort. The larger result was the risk. On inputs whose keys are half in runs of two and half in runs of 64, the pass reads a mean of 4.4, under six, while the long half saves the record 10,052 comparisons; with runs of 512 for the long half, 74,000, and switching the record off there cost 31%. Over every input the best mean threshold was three: keep the record for everything but runs of two.
That essay’s closing section said why. The record’s value on an input lives in its long runs, and a mean is a count of runs, which short runs dominate. It proposed counting the long runs directly: let the pass count the keys that lie in runs of at least , and keep the record when that share is at least . The prediction: at , and of a tenth keep the record on every uneven input and drop it on even runs of two and four, bringing the worst cost over every input from 0.2% to under 0.05%, at every rate. The named risk: long runs that are long but few, one run of 64 among a thousand runs of one.
Five inputs made for the risk
Each input is sorted twice, once with the record kept and consulted through quiet registers and once without it, both after the pass and with the chains, as before; the cost of a sort at rate is its comparisons times plus, if the record is kept, the register words it reads. The better choice on an input is whichever of the two costs less, and a switch’s cost on an input is measured as a share above that better choice. The inputs are the earlier essay’s twelve — even runs of 2, 4, 8, 16, 32, 64 and 256 keys, and five inputs of two halves — and five new ones aimed at the risk: three runs of 32 among runs of two, a tenth of the keys; four runs of 64 among runs of two, a quarter; two runs of 64 among runs of four, an eighth; one run of 256 among runs of four, a quarter; and one run of 64 among single keys, a sixteenth.
The pass sees runs as they lie, not as they were built — the same pass a pass repaid by the scans after it gave the sort, now read for more than its count. Adjacent pieces join when the last key of one is below the first of the next, so on even runs of four 2.3% of the keys sit in runs of eight or more, and on the input built from single keys the random order makes its own runs of about two. The share the switch reads is the share of keys in runs the pass actually finds, which is all a sort could know before its first scan.
The hero plate is that share against what the record saves, at . Every input where the record is worth keeping has at least 15% of its keys in runs of eight or more; every input where it is not has at most 9%. A switch at a tenth falls in the gap between them and chooses right on all seventeen.
What the mean could not separate
The mean run mixes the two kinds of input: at three word reads a comparison the record loses on inputs with a mean of up to 4.05 keys and gains on some with means as low as 3.16, so no threshold on the mean can choose right on all of them; the best, three, chooses wrong on one in seventeen. The plate is the earlier essay’s diagnosis drawn with the new inputs added. Four runs of 64 among runs of two read a mean of 3.16 and the record saves 1.4% there; even runs of four read 4.05 and the record loses 0.17%. A threshold between those means would have to sit both above 4.05 and below 3.16.
The mean’s best threshold copes by giving up the cheap case. At three it keeps the record on every input but runs of two, and pays on even runs of four, the one input it gets wrong, 0.18% of the sort. That is a small number, and it is the worst any input costs that switch. The earlier essay measured the price of a switch that tried for more — a threshold of six — at 31% on the uneven inputs, and the mean has no setting between giving up runs of four and giving up the uneven inputs.
The share has a setting. The record’s value grows with the keys in long runs: on an input with a quarter of its keys in runs of 64, those keys are where the record saves comparisons, and the other three quarters, in runs of two, are where it reads words for nothing. The share counts exactly the part that pays, so on the hero plate the inputs sort themselves by what the record is worth, in a way the mean does not.
Every setting at three word reads
At three word reads a comparison the share switch on runs of eight at a tenth leaves nothing — it chooses the better of on and off on every input — while the mean’s best threshold, three, leaves 0.175%; the share’s neighbours are nearly as good, and the settings that fail fail on the inputs either side of the gap. The prediction holds at its own rate and by more than it claimed: under 0.05% was predicted, and nought is measured. A share of a twentieth on runs of eight leaves 0.066%, on the input with three runs of 32 among runs of two, whose 9.4% of keys in long runs is just under a tenth and whose record loses 0.07% at this rate. A share of a fifth leaves 0.58%, on two runs of 64 among runs of four, which at 15% is just over the gap’s other side.
Runs of sixteen behave nearly the same, shifted. The input whose verdict differs is even runs of eight: every key lies in a run of eight and none in a run of sixteen, so at the switch drops the record there, and at three word reads a comparison the record saves 0.23% on runs of eight. That is the worst does at its best share, 0.23%.
The shape of the grid is the hero plate’s gap seen from the other side. Any share between 9.4% and 14.8% of keys in runs of eight separates the inputs at this rate, and a tenth is inside it with a margin of about a point on one side and five on the other. The margin is thin on the side of the input with three runs of 32. That input was built to sit near a tenth, and it does.
A different number at every rate
The right share moves with the rate: the best switch is runs of 16 at a fifth, then 16 at a tenth, then 8 at a tenth, then 8 at a hundredth, at one to four word reads a comparison; runs of eight at a tenth is right only at three, and at one word read a comparison it leaves 1.2% on runs of eight. The prediction’s last clause — right at every rate — fails. At a cheaper word the record pays on more inputs and the bar for keeping it falls; at a dearer word it pays on fewer and the bar rises. A share chosen at three is in the gap at three, and the gap moves.
At one word read a comparison no share switch measured decides every input. The best, runs of sixteen at a fifth, leaves 0.47% on an input of half runs of four and half of 32, where 50% of keys are in runs of sixteen or more and the record still loses at that rate, because the reading on the short half outweighs the comparisons saved on the long. At two, three and four word reads a comparison some setting is exactly right. The mean’s best threshold is worse than the best share at every rate, by 1.1 points at one word read and by 0.13 at four.
The stakes are small at every rate, and the plate should be read with that in mind. The largest cost any of the three switches on the plate leaves on any input is under two per cent of a sort. What the switch is for is the large cost it avoids: on the input with half its keys in runs of 512 the record saves 23.6% of the sort at three word reads, and a switch that drops it there — the mean’s at six — gives that back.
The few long runs
On inputs whose long runs are few the record’s value changes sign with the rate: one run of 64 among single keys costs the record 1.49% at one word read a comparison and saves 0.16% at four, and even runs of eight turn from loss to gain between two and three — no share threshold fixed in advance can follow both. The risk the proposal named is real, and it is a fact about rates rather than about the share. One run of 64 among single keys puts 6.3% of the keys in a run of eight or more; at three word reads a comparison the record loses 0.02% there and the switch, below a tenth, rightly drops it. At four, the record gains 0.16% and the switch still drops it. A share set low enough to keep it at four would keep the record at one word read a comparison on that input, where it loses 1.49%, and on every input with more of its keys in long runs, five of which lose at that rate too.
The plate also shows why these inputs are the hard ones. Each line crosses zero somewhere in the range of rates, because on each the record’s saving and its reading are of the same size. On inputs with many keys in long runs the line is far above zero at every rate and any switch keeps the record; on even runs of two it is below zero at every rate and any switch drops it. The decision is only ever difficult on inputs where it is worth little.
Of the five inputs built to defeat the share, none is decided wrong at three word reads a comparison; four are decided wrong by runs of eight at a tenth at some other rate, and one — four runs of 64 among runs of two — is decided wrong at one word read even by the best share for that rate. The risk was that a share would be fooled by structure. What it is fooled by is price.
Every verdict
The record pays on 8, 12, 13 and 16 of the seventeen inputs at one to four word reads a comparison, and the switch on runs of eight at a tenth disagrees with the better choice on 5, 1, 0 and 3 of them. The table is the whole result in one place. Reading down a column, the inputs where the record pays are a set that grows as words get dearer — not in the sense of the record getting better, but of the comparisons it saves being worth more words each. Reading across a row, nine inputs never change their verdict; the eight that do are the inputs with few long runs and the even runs of four, eight and sixteen.
The switch’s mistakes are where the verdicts move. At one word read a comparison it keeps the record on runs of eight and sixteen and on three of the uneven inputs, where at that rate the record does not pay; at four it drops it on runs of four and on two of the few-long-runs inputs, where it now does. At three it makes none. A switch that wanted to be right at every rate would have to read the rate as well as the runs, which is to say it would have to be told the price of a word.
What the pass knows and what it is not told
The question the proposal closed on was whether one more number from the pass, chosen for what the record is worth, is enough to decide, or whether the decision belongs to each run. On these inputs one number is enough — the share of keys in runs of at least eight — but only for a given rate, and the threshold on that number is a statement about the rate. That is not a failure of the share. It is the same thing the price of remembering an answer found from the other end: the record is worth keeping when a comparison costs more than the words it takes to avoid one, and no property of the input alone can say which that is.
The per-run alternative the proposal mentioned is still open in principle. The runs too short to drop found that forgetting short runs inside the record made it dearer, not cheaper, because the record’s bookkeeping is shared across runs; a decision per run would face the same sharing. The share switch avoids it by making one decision for the input, and the measurement says that one decision, made from the right number, is enough at any single rate.
What changes the decision is the machine, and the machine is the one input the pass never reads. A sort deployed where a word read is cheap relative to a comparison — keys that are long strings, compared character by character — sits at a low rate; one comparing machine integers in registers sits at a high one. A table of the best share at each rate, measured once, would let the sort choose its threshold from the type of its keys.
What the measurement leaves out
One size, 1,024 keys. The record’s saving and the registers’ reading both scale with , but not in the same way on every input; a larger array would move the gap.
Four rates, all integers. The best share is measured at one, two, three and four word reads a comparison; between them it was not.
Seventeen inputs, five of them built for this question. A real input’s runs are not pieces of a random permutation each sorted; inputs drawn from real data, such as logs appended in near-order, were not measured.
Still open: a threshold that reads the price
The share switch is right at three word reads a comparison and wrong at the others, and the plates say why: the inputs near the gap are those whose record saves about as much as it reads, and where that balance falls depends on the rate. The pass could compute that balance directly instead of a proxy for it. It knows, as it goes, the runs it finds; the essays on this record have measured what a run of each length saves in comparisons and costs in register words. A switch could sum, over the runs the pass finds, a predicted saving and a predicted reading for each — a small table indexed by run length — and keep the record when the predicted saving times the rate exceeds the predicted reading.
The measurement that follows builds that table from even runs, where saving and reading are measured exactly, applies it to every input here at every rate, and charges the switch’s own arithmetic as word reads. The prediction is that it is right on all seventeen inputs at all four rates, and that its worst cost anywhere is under 0.05%, because it reads the one quantity the share stands in for. It could fail on the halves: the saving on a run depends on the runs around it, since the two-ended sort’s scans cross run boundaries, and a table built from even runs may misprice a long run among short ones. The question is whether the record’s value on an input is a sum of what its runs are worth one at a time, or whether the runs interact enough that only sorting the input tells.
Named alongside this one
Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.
- A filter that reads the word it saves bit vector · comparison count · natural run · prediction · selection sort · space time trade
- A record of stretches, not pairs comparison count · prediction · selection sort · space time trade
- A record the size of a pass's minima comparison count · prediction · selection sort · space time trade
- The record measured where it would run comparison count · prediction · selection sort · space time trade
- Two swaps a pass, and the stretches hold comparison count · prediction · selection sort · space time trade
- A request that reads the input first comparison count · natural run · space time trade
The objects this essay names
Each one links to every other essay that touches it.
Bit vectorComparison countNatural runPredictionSelection sortSpace time trade