A pass repaid by the scans after it

A run answers what nobody asked gave bidirectional selection sort a record of what it had learned about neighbouring positions: for each pair $p$ and $p+1$, whether the key at $p+1$ is known to be smaller, known to be larger, or unknown. A stretch of pairs known in one direction is a run, and any question about two positions inside a run is answered from which of them comes first. Beside the two chains of the previous pass, that record took sorted keys from 263,167 comparisons at 1,024 keys to 2,045, two a key. Every one of those 2,045 was made in the first scan, which met each neighbouring pair one position too late to use it.

The essay closed by proposing the obvious repair. Before the first scan, compare every key with the one after it: $n - 1$ comparisons, and the whole record of runs is known before any question is asked. It predicted three things. Sorted and reversed keys would fall to about $n$, the pass alone. Random keys would rise by the pass’s $n$, which their short runs could not repay. Organ-pipe keys, two runs meeting in the middle, would fall further, because every question of the first scan would be answerable from the start. And somewhere between random and sorted there would be a run length at which the pass pays.

The first prediction holds exactly. The other two hold in direction and fail in their reason, and the reason turns out to be the interesting part: almost none of what the pass buys is bought in the first scan.

The pass, and nothing else changed #

The sort is the earlier essay’s, unchanged. Each pass scans the unsorted range from its low end, asks each key whether it is smaller than the current minimum and, if not, whether it is larger than the current maximum, then swaps the minimum to the low end and the maximum to the high end. The record keeps the previous pass’s two chains of minima and maxima and the known order of neighbouring pairs, and a swap forgets the pairs on either side of each position it moves. The chains answer their own side’s repeated questions first, and the runs answer whatever lies inside one of them.

The only change is the pass. Before the first scan, the sort compares the key at $p$ with the key at $p+1$ for every $p$, $n - 1$ comparisons, each counted as made, and each recorded as the pair’s known order. Nothing is skipped: a pass over a random input pays its full $n - 1$ like a pass over a sorted one. Every answer the record gives afterwards is checked against the keys, and every comparison the sort could not answer is counted, so the totals below include the pass.

Exactly one pass, on the two monotone inputs #

With the pass first, sorted keys cost 1,023 comparisons at 1,024 keys and reversed keys 1,023 — exactly $n - 1$, the pass and not one comparison more. The pass finds a single run covering the array, and every question of every scan lies inside it. On sorted keys the swaps move nothing, so the run is never broken. On reversed keys every swap exchanges the two ends of the range, which forgets the pairs at the ends. The questions all lie between the new ends, so the run still covers them.

Reversed keys gain nothing from the pass because they did not need it. Without the pass, reversed keys already cost 1,023. Each key the first scan reaches is a new minimum, and the question that discovers it is a question about the key and its neighbour. So the first scan learns the whole run as it goes, one pair per comparison, and the chains answer everything after. Sorted keys were the case the pass was proposed for. Their first scan asked 2,045 questions, two for every key but the first, and learned each neighbouring pair one question too late to use it. The pass asks 1,023, one for each pair, and after it no scan asks anything. The saving, 1,022, is one comparison a key.

That makes the sort’s best case linear and tight. No sort can certify that $n$ keys are in order in fewer than $n - 1$ comparisons. Each neighbouring pair must be compared directly, since no other key lies between the two in value and so no chain of other comparisons can relate them. A selection sort with a record of runs, given one pass, meets that floor on both monotone inputs. Where insertion sort actually wins found insertion sort’s case resting on memory traffic, not comparisons; on this count, a selection sort now ties it on sorted input.

Random keys, and the comparisons that come back later #

On random keys the pass costs 1,023 comparisons at 1,024 keys and the sort makes only 236 more: the first scan repays 25, as the prediction implied, and the 511 scans after it repay 762, which the prediction never looked for. At 4,096 keys the pass costs 4,095 and the sort makes 959 more. In both cases about three quarters of the pass comes back, and nearly all of it after the first scan is over.

The first scan repays almost nothing, as predicted. The record’s runs on random keys are short, about two keys each, since a random input has a natural run of mean length two (501 natural runs among 1,024 keys here). The first scan’s questions are about the current minimum or maximum and the key being scanned. Those two positions are usually far apart, and a short run between them cannot relate them.

The later scans are another matter. A known neighbouring pair survives until a swap moves one of its two keys, and each pass makes at most two swaps, forgetting at most eight pairs. The pass sets down a thousand of them, and they erode slowly. Meanwhile each later scan keeps meeting the situation a neighbouring pair is good for: the current extreme sits at position $j - 1$, because it was just found there, and the scan asks about the key at $j$. Without the pass that question is asked and its answer recorded. With it, the answer is already there. Each such question is worth one comparison, and the pass’s thousand pairs answer about 760 of them over the sort’s life before swaps wear them away.

So the prediction’s arithmetic was right and its accounting was wrong. It charged the pass against the first scan, because that is where the earlier essay found the run record’s missing comparisons. The pass is a statement about the input that stays true until a swap disturbs it, and a selection sort, which disturbs only two positions a pass, gets to use it for a long time.

Organ pipes, repaid in every scan #

On organ-pipe keys the pass saves 43,776 comparisons at 1,024 keys, 17% of the sort’s work: 1,534 in the first scan and 43,265 in the scans after it. The prediction expected the gain to be the first scan’s. The first scan does gain, from 2,045 comparisons to 511, but that is 3% of the total saving.

The rest comes from the falling half. An organ-pipe input rises to the middle and falls after it. In the first scan the minimum is the first key and stays there, since the first key is the smallest of all. So the minimum’s questions are all about the first position and a distant key. The maximum moves along the rising half, one neighbour at a time, so the first scan learns the rising half’s pairs. In the falling half the maximum stays at the middle and the minimum at the start, and no question in that half is about two neighbours. Without the pass, nobody learns that the falling half is a run until swaps and later scans happen to relate its pairs one at a time. With the pass, it is known from the beginning.

That is visible in the plate as a gap that runs through most of the sort. Without the pass, a scan a quarter of the way through makes 833 comparisons; with it, 514. The gap closes only as the range narrows to the middle, where both halves have been consumed. Split by halves of the sort, the first 256 passes save 42,047 comparisons and the last 256 save 2,752.

Every one of the saved comparisons is a question never asked before. With the pass, the record answers 130,948 questions the sort had not asked, against 86,842 without; the difference, 44,106, is 98% of the 44,799 comparisons the scans no longer make. The repeated questions are answered at the same rate either way, 84.5%. The pass adds no memory of old answers. It adds knowledge of the input, and a run answers by transitivity, which is the distinction the earlier essay drew and this measurement sharpens: the questions a sort asks twice are the chains’ business, and the questions it has never asked are the runs’.

Runs of four keys, at every size #

On inputs made of equal sorted runs, the pass loses 0.33 comparisons a key at runs of two, comes within 0.05 a key of even at runs of four, and saves 0.18 a key at five and 2.15 at sixteen — and the curve is the same at 256, 1,024 and 4,096 keys. The inputs here are a shuffle of the keys cut into pieces of a stated length, each piece sorted ascending, so the run length is set exactly and the values in neighbouring runs interleave at random.

The break-even’s independence of $n$ is the result worth keeping. The pass costs one comparison a key. What it saves is also a count a key: each run of length $L$ answers, over the sort’s life, a number of questions that depends on $L$ and not on how many other runs there are. Below four, a run answers less than one question a key before swaps break it. Above four, more. A sort that could see its input’s mean run length before deciding would make the pass exactly when that length is above four, and the decision would hold at every size.

A sort can see it, cheaply, and the pass is how. The pass counts the input’s runs as a side effect. That count is what a run is a property of the input argued was the right measure of presortedness, and here it is also the number that decides whether the pass was worth making. The decision comes one pass too late to avoid the pass’s cost, but at a third of a comparison a key on the worst input, the loss is small against the 2.15 a key gained at runs of sixteen.

What the pass leaves in memory #

On random keys the pass makes the record of runs forty times as large: at its largest 674 runs at 1,024 keys against 17 without the pass, and 2,733 at 4,096 against 25. Without the pass, the record holds only the pairs the scans happen to relate, a handful at a time. The pass relates all of them at once, and a random input’s runs are short, so the record holds about one run for every three keys and keeps most of them until swaps erode them.

This is the cost the comparison count does not see. A run is a start, an end and a direction, three words, so the record at 1,024 random keys grows from 51 words to about 2,000. It is still small against the keys themselves. But it is a cost paid on exactly the input where the pass loses, to answer 762 questions over the life of a sort that makes 261,688 comparisons. On organ-pipe and sorted keys the pass adds no runs at all, 19 and one, so the memory cost falls entirely on the inputs that gain nothing.

A record that kept only runs longer than some length would cut that cost. On random keys it would discard nearly everything, which loses little, since the short runs answer three quarters of a comparison a key. But the record that forgets on purpose found that a record’s worth depends on what it throws away, and nothing here measures whether a run of two answers more than its share. That is left for the closing section.

Linear at one end, quadratic everywhere else #

The pass makes the two-ended selection sort optimal on sorted and reversed input, and that is as far as it goes. At runs of sixteen keys, the input on which the pass pays best of those measured, the sort still makes 265,132 comparisons at 1,024 keys, about $n^2/4$. A merge of the same input’s 64 runs, pairwise, needs at most $n \lceil \log_2 64 \rceil$, or 6,144. Even organ-pipe keys, two runs, cost 213,148 comparisons with every help the record can give, where one merge of the two runs costs at most 1,023.

The original question was the run length at which a selection sort stops being the wrong sort. The measurement answers it: there is no such length short of one run covering the whole input. The record of runs answers questions inside a run, and a selection sort’s questions cross runs constantly, since the minimum of the remaining range is wherever it happens to be. The pass and the record move the sort along a line from $n^2/2$ toward $n^2/4$ and, at one end, collapse it to $n$. They do not change its shape. When galloping pays and the cheap tail and the expensive merge measured sorts whose shape is set by runs; this one’s is set by its scans.

That is not a reason to have measured nothing. The strand began by asking what a sort’s comparisons are worth remembering, and the price of remembering an answer set the record’s cost against the comparisons it saved. The pass adds the other half: knowledge that was never an answer to anything, bought deliberately, and paid back over the sort’s whole life rather than at once. That is the same trade a request that reads the input first made for a merge sort’s buffer, where one pass bought a buffer sized to the input and was worth about a comparison a key. Here the same pass is worth $-0.33$ to $+2.15$ comparisons a key, and its value is set by the input’s run length alone.

What these counts do not cover #

One shuffle a size, one draw of runs. Each random input and each input of equal runs is a single shuffle at each size. The change at runs of four is within 0.05 a key of zero at every size, and that is the precision the break-even is stated to; whether it is just under four or just over is not resolved.

Equal runs, all ascending. The run inputs have every run the same length and the same direction. A real input with runs of mixed length and direction would mix the regimes, and nothing here says whether the break-even is set by the mean length, the median or the long tail.

Comparisons, not reading. The record is scanned to decide whether two positions share a run, and the pass makes that scan longer on random keys, where the record holds forty times the runs. Counting instead of timing is why every number above is a comparison; on a machine, the record’s reading is where the pass’s gain on random keys would go first.

Distinct keys. Every input is a permutation, so no neighbouring pair is equal and a pair’s known order has two values. With ties, a third would be needed.

Still open: a record that keeps only the runs worth keeping #

On random keys the pass leaves 674 runs in the record and gets back three quarters of its cost from them; on runs of four and more it pays outright. The runs that pay are not all the runs. A run of two keys relates one neighbouring pair and answers a question only when the scan’s current extreme happens to sit at one end of it; a run of thirty relates thirty positions to each other and answers questions across its whole length. The record could keep a run only if it is at least some length, discarding the rest when the pass finds them and when swaps cut a long run into short pieces.

The measurement that follows gives the pass that rule and counts comparisons and the record’s largest size at minimum kept lengths of two, three, four and eight, on random keys and on the equal-run inputs. The prediction is that keeping only runs of three and longer cuts the record on random keys by about two thirds and gives back under a tenth of the 762 later-pass comparisons, because a run of two is mostly a single pair that the scan rarely lands on. On runs of four and more nothing should change, since every run there is kept. It could fail if the short runs matter more than their length suggests: a run of two between two longer runs of the same direction is what joins them once the scan relates its ends. The number that decides it is how many comparisons each discarded run would have answered, set against the three words it occupies.