The runs too short to drop

A pass repaid by the scans after it gave the two-ended selection sort one pass before it starts: compare every key with the one after it, $n - 1$ comparisons, and record the order of each neighbouring pair. On sorted and reversed keys that pass is the whole cost. On random keys it cost 1,023 comparisons at 1,024 keys and the sort made only 236 more than without it, because the scans after the first kept meeting a pair the pass had already ordered. The price was memory. A record that held at most 17 runs without the pass held 674 with it, about one for every three keys. At three words a run, a start, an end and a direction, that is about 2,000 words to repay 787 comparisons in a sort that makes 261,688.

That essay’s closing section asked whether all of those runs earn their place. A run of thirty keys relates thirty positions to one another and can answer a question about any two of them. A run of two keys relates one pair, and answers a question only when the question is about exactly those two positions. The proposal was to keep a run only if it covers some minimum number of keys, discarding shorter ones when the pass finds them and when a swap cuts a long run into pieces. It predicted that keeping only runs of three keys or more would cut the record on random keys by about two thirds, and give back under a tenth of the 762 comparisons the later scans had repaid. On inputs whose own runs are four keys or longer it predicted no change at all, since every run there would be kept. It named the way it could fail: if a run of two answers more than its length suggests.

The rule, and where it is applied #

The sort is the earlier essay’s. Each scan of the unsorted range finds its minimum and maximum, asking each key whether it is smaller than the current minimum and, if not, whether it is larger than the current maximum; the two are then swapped to the ends. The previous scan’s chains of minima and maxima answer repeated questions first, the record two swaps and the stretches hold built for both ends, and they are what the questions a sort asks twice showed a selection sort is mostly made of. The record of runs keeps, for each neighbouring pair of positions, whether the later key is known to be smaller, known to be larger, or unknown, and a swap forgets the pairs on either side of each position it moves. A question about two positions is answered when every pair between them is known in the same direction. Every answer is checked against the keys.

The one change is the rule. At the end of the pass between neighbours, and again at the end of every scan after its swaps, every maximal stretch of pairs known in one direction that covers fewer than a stated number of keys is forgotten. A minimum of two keys keeps everything and is the earlier essay’s sort exactly. Minimums of three, four, five and eight are measured.

Two thirds of the record, and two thirds of the saving #

Keeping only runs of three keys or more, the pass adds 759 comparisons at 1,024 random keys instead of 236: the threshold gives back 523 of the 762 comparisons the later scans had repaid, more than two thirds. The prediction was under a tenth. It was off by a factor of seven, and the direction of the error is the finding.

The record does shrink as predicted. At its largest it holds 246 runs where it held 674, 63% fewer, close to the two thirds the proposal expected. The memory and the comparisons fall together, almost in proportion, and that is the first sign that the short runs were not idle.

Raising the threshold further makes the pass worse than useless. At four keys the pass adds 1.06 comparisons a key, more than the pass itself costs; at eight, 1.25. A record that keeps only runs of eight keys keeps nothing at all on random keys, and so loses even the few runs the sort’s own scans would have found without any pass. The pass then buys nothing and the record’s absence costs a quarter of a comparison a key beyond it.

The curve is the same at every size. At 256, 1,024 and 4,096 keys the change a key differs by at most five hundredths at every threshold. A pass repaid by the scans after it found that the pass’s break-even run length does not depend on $n$, because what a run answers over a sort’s life is a count a key. The same reasoning carries the threshold: what a run of a given length answers is a property of the run and the scans that pass over it, and not of how many other runs there are.

What it costs in words, and what else could hold the same knowledge #

A record that keeps every run costs 2,022 words at 1,024 random keys; one that keeps only runs of three costs 738; and the knowledge of every neighbouring pair, written as two bits a pair, costs 64. The threshold was a way of making a list of runs smaller. The list was the wrong shape for what it held.

A run list spends three words on a run however long it is. That is economical when runs are long: sorted keys are one run and three words. On random keys the pass finds runs of two or three keys, so the list spends three words to hold one or two pairs. Writing each pair’s state directly, unknown, smaller or larger, takes two bits a pair whatever the input, $2(n-1)$ bits in all. At 1,024 keys that is 2,046 bits, 64 words of 32 bits, a thirty-second of the full run list and an eleventh of the list that keeps only runs of three or more.

The two representations hold exactly the same information when every run is kept, so the bit record makes the same comparisons the full run list does, 261,688 at 1,024 keys. The only rule above that costs less memory is the one keeping runs of five keys or more, at 57 words, and it adds 1.19 comparisons a key. Without the pass, the sort’s own record peaked at 17 runs, 51 words. So the bit record costs thirteen words more than the record the sort grows by itself, and with it the pass is repaid by three quarters.

What the measurement does not count is the price of asking. A run list answers a question about positions $i$ and $j$ by finding the run that holds $i$ and checking that it reaches $j$. A bit record answers it by checking that every pair from $i$ to $j$ has the same state, sixteen pairs to a 32-bit word. Both were counted here as free, as the earlier essays counted the record. Which is cheaper depends on how far apart the asked positions are.

Which runs answer #

Runs of two keys answer 599 of the 1,221 questions the record answers at 1,024 random keys, almost half, at 1.39 answers for every such run the pass set down. Longer runs answer more each: 2.27 for a run of three, 3.02 for a run of four. But the pass sets down 432 runs of two, 173 of three and 55 of four, and the short runs’ numbers carry them. That is the shape of a random sequence’s runs: nearly two thirds of its maximal monotone stretches cover two keys, and a stretch of four is rare.

Each answer is attributed to the longest run that held the asked pair at the moment it was asked, so a run that a later scan lengthened by learning a neighbouring pair is counted at its new length. The pale bars count only the runs the pass set down. A few of the solid bars’ answers come from runs the scans built, and runs of six keys are too few to read anything from, four runs answering 24.

The proposal’s number to decide it was how many questions each run would answer, set against the three words it occupies. For a run of two that is 1.39 answers for three words, close to half a comparison a word. Dropping all of them saves 1,284 words at their largest and gives back 523 comparisons: 0.41 comparisons for each word saved. Whether that trade is worth taking depends on what a word costs against a comparison, which this sort cannot say. But it is the trade, and it is nothing like the free one the prediction described.

The question a run of two is for #

Three quarters of the questions the record answers on random keys are about two neighbouring positions: 74% at 1,024 keys, 75% at 4,096. The proposal’s model of a run of two was a pair that answers a question only when the scan’s current extreme happens to sit at one end of it. That is right, and it happens constantly.

A scan reaches position $j$ and asks whether the key there is smaller than the current minimum, or larger than the current maximum. Whenever the scan has just found a new extreme at $j-1$, the next question is about $j-1$ and $j$, two neighbours. A scan finds a new minimum or maximum only a few times on random keys, but it does so in every scan, and the sort makes hundreds of scans; every one of those moments asks a neighbour question, and the pass has already answered it. The earlier essay found this was where the pass’s saving came from, in the scans after the first. This plate is how much of the record’s work it is.

A run of two keys exists to answer exactly that question. It relates one neighbouring pair, and the commonest question a selection scan asks is about one neighbouring pair. The proposal priced a run by how many positions it relates, which is the right price for a question about two distant positions. For a question about two neighbours, the shortest run is as good as the longest. So the runs the threshold drops are the runs best matched to most of the questions.

Inputs whose own runs are long #

On inputs made of sorted runs of four keys, keeping only runs of three or more costs 0.40 comparisons a key, and on runs of sixteen it still costs 0.17. The proposal predicted no change on these inputs, since every run the pass finds there is at least four keys long. That is true of the runs the pass finds, and the pass is not where the record’s runs come from for most of the sort.

The inputs are a shuffle of the keys cut into pieces, each piece sorted ascending. The pass finds the ascending pieces and, between each two, a single descending pair, a run of two keys. These are the inputs on which a run is a property of the input measured presortedness by the count of runs, and on which a merge that gallops, as when galloping pays found, does its best work. Those boundaries are 255 runs at pieces of four, and the threshold drops them. But over the whole sort it drops 3,516 runs. The other 3,261 are runs that appear later, when a swap cuts a long run and leaves a short piece on either side of the moved position, and when a scan learns a neighbouring pair that has no known neighbour of its own. Thirteen dropped runs in fourteen are made after the pass, and dropping them is where the 0.40 comes from.

The threshold’s cost falls as the input’s runs lengthen, because a long run cut by a swap usually leaves pieces long enough to keep. At pieces of sixteen keys the threshold drops 2,701 runs and costs 0.17 a key. The cost does not reach zero within the lengths measured.

Words against comparisons #

Every threshold sits on a line from many words and few comparisons to few words and many, and the bit record sits off that line, with the fewest comparisons and nearly the fewest words. At 4,096 random keys the full run list peaks at 8,199 words and the bit record is 256. Keeping runs of three or more costs 3,129 words, twelve times the bit record, for 0.76 comparisons a key against 0.23.

The run list grows with the number of runs, which on random keys is a third of $n$. The bit record grows with $n$ at two bits a key. Both are linear, and they differ by the constant: three 32-bit words, 96 bits, for every three keys, against six bits. The record that forgets on purpose found that a cache of recent comparisons kept nine repeated answers in ten for an eighth of a full table’s bits. Here the reduction comes from a change of representation rather than from forgetting.

The earlier essay asked whether a record’s worth depends on what it throws away, and this record answers that the short runs are worth keeping. A run answers what nobody asked introduced runs as a compression of the chains’ links, one interval for a stretch of links, and on sorted and reversed keys that compression is enormous. On random keys there is nothing to compress. Each run is one or two pairs, and the interval costs more than the pairs it stands for.

What the counts depend on #

Comparisons, not time. The sort’s work is counted in comparisons between keys. Consulting the record, whether a run list or a bit record, is counted as free, and so is applying the threshold.

One shuffle a size. Each size and input kind is one permutation. The curves at three sizes agree to three hundredths, which says the per-key picture is stable; it does not give an error bar on any one number.

A threshold applied at scan boundaries. Short runs are dropped at the end of the pass and the end of each scan. Within a scan, a newly learned pair survives until the scan ends, and some questions are answered by pairs that the threshold will drop a moment later. A rule applied the instant a pair is learned was not measured.

Still open: what it costs to consult two bits a pair #

The bit record keeps everything the full run list keeps, in a thirty-second of the memory, and this measurement counted both as free to read. They are not equally cheap. A run list answers a question about positions $i$ and $j$ by finding the run that holds $i$, a binary search over the runs, about ten steps on 674 runs, and comparing that run’s end with $j$. A bit record answers it by reading the pairs from $i$ to $j$, sixteen to a 32-bit word, and checking that they all have one state.

The two costs part ways on distance. Three quarters of the questions answered are about two neighbours, one word of the bit record against ten steps of a search. But a scan asks every question, answered or not, and most are about the current extreme and a key far from it. A bit record discovers that it cannot answer such a question at the first pair that breaks the run, which on random keys is within a word or two. The measurement that follows counts, for every question the sort asks, the words a bit record reads and the steps a run list’s search takes, on random keys and on inputs of long runs, with and without the pass. The prediction is that the bit record reads under two words a question on random keys and stays cheaper than the run list’s search at every size, and that on sorted runs of sixteen keys or more the run list wins, because there a question about two distant positions inside one run costs the bit record a word for every sixteen keys between them. The question is whether two bits a pair is the right record for this sort everywhere, or only where its runs are short, and whether a sort that read the pass’s run count first could choose between them, the way a request that reads the input first chose its buffer from what one pass had seen.