Two swaps a pass, and the stretches hold

A record of stretches, not pairs gave selection sort a memory of its own past comparisons in the shape the sort makes them. A pass scans the unsorted keys keeping the smallest seen so far, and the sequence of keys that were the smallest at some moment is the pass’s chain. Each link covers a stretch of positions, the keys compared with it while it was current, ending with the key that beat it. Kept for one pass, the chain answered 99.3% of the comparisons a full table of past questions would have answered at 1,024 keys, in 312 bytes rather than 256 KB. The one failure the essay predicted was a key moved by the pass’s swap into the middle of a stretch. It cost 0.04% of the table’s skips.

That essay closed by asking whether the result belonged to the stretch or to selection sort’s one swap a pass. Bidirectional selection sort is the test. It finds the minimum and the maximum in the same scan and places both, the minimum at the front of the unsorted range and the maximum at the back. So a pass keeps two chains, and it makes two swaps, each of which can land a key where the other chain’s stretches reach. The prediction was that each chain would behave like the single one and that the second swap would break more stretches, and it named the number that would decide: if two swaps drive the broken share into whole per cent, a stretch is something only a one-sided scan keeps intact.

Two chains out of one scan #

The scan is the usual one. Each key is compared with the current minimum, and only if it does not beat the minimum is it compared with the current maximum. A key that beats the minimum is below every key seen, so it cannot beat the maximum and the second question is skipped. That is how the sort saves comparisons, and it makes the maximum’s chain a little different from the minimum’s.

The minimum’s stretches are contiguous; the maximum’s have holes. A minimum’s link covers every position scanned while it was current, since every key is compared with the minimum first. A maximum’s link covers the same kind of run, except for the positions where a new minimum was found, because those keys were never put to the maximum. A record that answered a question inside a hole would be answering one it never asked. The record here stores, beside the two chains, the positions where the minimum changed, and never answers a maximum’s question at one of them. The sort checks every answer the record gives against the keys and checks that every answered question was asked in an earlier pass. Neither check fires on any input measured here, and the hole turns out to be guarded twice over, which the breakage below explains.

The swaps are where the two chains meet. The minimum’s swap moves the key at the front of the range to the minimum’s position, and the maximum’s swap moves the key at the back to the maximum’s position. Both positions lie inside the other chain’s stretches. The first pass in the figure shows it: position 42, where the maximum ended, lies inside the minimum’s final stretch from 21 to 47, and position 20, where the minimum ended, lies inside the maximum’s stretch from 7 to 42, as one of its holes. The one-sided sort had one moved position a pass that could spoil a stretch. This sort has two, each in the other chain’s territory, and that was the reason to expect more breakage.

Each chain answers its own side #

Each chain answers its own side’s repeats nearly as the single chain does: 99.1% for the minima and 99.2% for the maxima at 1,024 keys, against 99.3% for the one-sided sort. The three lines rise together with the size of the array, from about 94–95% at 128 keys to 99.7–99.8% at 4,096, and the gap between the two-ended sort’s chains and the one-sided chain closes as they rise. That part of the prediction holds as stated. The two chains are independent enough that each is, for its own side, the record the one-sided essay described.

The questions divide almost evenly. At 1,024 keys the table would skip 130,983 questions put to a minimum and 130,838 put to a maximum, and the chains answer 129,829 and 129,775 of them. The symmetry is not guaranteed by the scan, which asks the minimum first and the maximum only sometimes. It comes out even because on random keys a new minimum is rare, about the harmonic number of the range a pass, so nearly every key is asked both questions.

Kept alone, each chain answers half. A record of only the minima catches 49.6% of the two-ended sort’s repeats at 1,024 keys, and a record of only the maxima 49.6%. Neither chain answers any of the other side’s questions, and the two together catch what the two separately would. That is also a check on the record. If the chains had been answering each other’s questions, the two halves would sum to more than the pair.

The comparisons left for the sort to make are about the same in both sorts. With the record, the two-ended sort makes 261,886 comparisons at 1,024 keys against 267,275 for the one-sided sort, out of roughly 520,000 each would make without one. The questions a sort asks twice found that about half of selection sort’s comparisons repeat an earlier one. Asking for both ends at once does not change that proportion. It rearranges which pass asks which question and leaves the redundancy where it was.

A tenth of a question a swap #

Two swaps a pass break 0.044% of the repeated questions at 1,024 keys, against 0.040% for one swap, and both shares fall roughly as 1/n. At 128 keys the two-ended sort’s share is 1.24% — whole per cent, as predicted — and it is 0.84% for the one-sided sort. By 512 keys both are near a tenth of a per cent and by 4,096 they are under a hundredth. The prediction’s threshold is crossed at the smallest size measured and nowhere else.

The reason is a count that barely changes from one sort to the other. A swap spoils about a tenth of a question on average: 0.11 at 1,024 keys for the two-ended sort’s swaps taken together, and 0.10 for the one-sided sort’s single swap. A pass of the two-ended sort makes two swaps and so spoils twice as much, but it has half as many passes, since each pass places two keys. The total number of broken questions is 116 against 104, and the number of repeated questions is 261,821 against 258,290. The broken share is set by the number of swaps over the number of repeats. The swaps grow as $n$ and the repeats as $n^2$, so the share falls as $1/n$ whatever the sort does with its swaps.

The 116 broken questions at 1,024 keys divide between the sides. Seventy were questions put to a minimum and 46 were put to a maximum, and forty of the 46 fell in a hole. Each of those forty keys had beaten the minimum in the previous pass, so it was never compared with the maximum. This time it did not beat the minimum it met, and every one of the forty also had a moved key at one of its two positions. No question reached a hole with nothing moved, on any input or at any size measured. A key that beat a minimum last pass beats it again unless a smaller key has arrived ahead of it, and the only keys that arrive are the ones the swaps carry. So the hole check never refuses anything the swap check would not already refuse. It is kept because it costs a set lookup, and a record without it stays correct only because of the swap check.

The swap that carries its history #

The prediction expected the second swap to be the dangerous one, since it lands in the minimum chain’s territory. Counted by the swap that moved the offending key, the minimum’s swap caused 105 of the 116 breaks at 1,024 keys and the maximum’s swap 11. The same division holds at 128 keys, 36 against 6, and at 4,096, 215 against 42. The swap added by the second chain is the quieter of the two, and the hole questions — the ones peculiar to two chains — are almost all the minimum’s swap’s doing.

What each swap moves explains most of that, though the explanation below is argued from the scan rather than isolated by a separate run. The maximum’s swap moves the key at the back of the range, the last key every pass scans. Unless a swap has moved it, it has sat at that position through every earlier pass. Each of those passes compared it with the pass’s minimum at the moment the scan ended, and, when it did not beat that minimum, with the pass’s maximum at the same moment. Both are keys the pass then placed. So every question it was ever asked was about a key that has since left the unsorted range. Moved to the maximum’s position, it meets keys it has never been compared with, and a question about a new pair cannot be a broken repeat.

The minimum’s swap moves the key at the front of the range, and that key’s history is the opposite. It sat near the start of every earlier scan, where the early minima of each pass were compared with it. Many of those minima are still in the range. Moved to the minimum’s position, deep in the scan, it meets them again. That makes it the one moved key likely to be asked a question it has been asked before, in a place where the previous chain says nothing about it. The one-sided sort has exactly this swap. Over its 1,023 passes it breaks 104 questions, and the two-ended sort’s minimum swap, over 512 passes, breaks 105: about 0.2 a swap against 0.1. The maximum’s swap breaks 0.02 a swap, and the two average out at close to the one-sided rate. That the average matches is partly a coincidence of these two numbers, and the reason the two-ended minimum swap is twice as destructive a swap as the one-sided one was not isolated.

Twice the links, still a logarithm #

At 1,024 keys the pair of chains holds 21 links at its longest, 63 words, and 12.7 links on a pass’s average; the one-sided chain holds 13 at its longest. From 128 keys to 4,096 the pair grows from 15 links to 29, and the growth follows the logarithm of $n$. A pass’s minimum chain has a link for every left-to-right minimum of its range, about $H_m$ for a range of $m$ random keys, and the maximum chain a link for every left-to-right maximum, about as many. A record the size of a pass’s minima found the harmonic number predicting the one-sided chain within 6% at every size. For two chains of $H_m$ links, averaged over the ranges the two-ended sort scans — from the whole array down to two keys, shrinking by two a pass — the prediction at 1,024 keys is 13.0 links, and the measured average is 12.7.

The average is higher than the one-sided sort’s 5.5 for a reason that has nothing to do with the second chain. The one-sided sort’s passes run from the whole array down to two keys, and its average includes all the short late passes. The two-ended sort stops halfway, when its two ends meet, so its shortest pass still scans half the array. At 63 words the record fits in eight cache lines. The record measured where it would run found the full table missing twice for every comparison it saved at 1,024 keys, and this record is too small for that to happen.

Sorted keys, the new worst case #

The one-sided chain’s weakness was reversed keys. Every scanned key beats the minimum before it, so every position becomes a link, and the chain holds a link a key. The two-ended record has that weakness and its mirror image. On reversed keys its minimum chain holds a link a key and answers every repeat. On sorted keys, where the one-sided sort never asks a question twice, the two-ended sort asks 261,633 questions it has asked before, and the maximum chain answers 99.8% of them from 1,025 links.

The sorted case repeats where the one-sided sort does not because the second question is new. The one-sided sort, scanning sorted keys, compares every key with the front key, which stays the minimum, and places it — nothing is asked again. The two-ended sort asks the same, and then asks each key whether it beats the maximum, which it does, every time. The maximum moves one position at every step and ends at the back, already in place. The next pass repeats the whole walk one position shorter at each end, so every question it asks the maximum was asked the pass before. A record of the maxima answers them all and needs a link at every position to do it. An adversary who controlled the order of the keys could make the one-sided record long by reversing them. Against the two-ended record, reversing or leaving them sorted both work.

Organ-pipe keys, rising to the middle and falling after it, give the two-ended record 84.3% of the repeats against 78.9% for the one-sided chain, at twice the links. The one-sided essay traced its loss there to questions last asked before the previous pass, which no chain of one pass can hold. A likely reason, not isolated here, is that the two-ended sort reaches the middle from both ends and so makes half as many passes over the same shape, leaving fewer of its questions unasked for more than one pass.

What the second chain changed and what it did not #

The result divides cleanly. What the second chain did not change is the soundness of a stretch as a record: each side answers its own repeats, and the breakage per swap is a tenth of a question whichever sort makes the swap. What it changed is the input on which the record is expensive. That is a property of which questions the scan asks, not of the record, and it could have been predicted from the scan alone. The record has one length for every run of consecutive new extremes the scan meets, and a two-ended scan meets runs in both directions.

Two pivots and what they cost found the analogous division for quicksort. Two pivots moved the comparison count down and the swap count up, and neither number was the whole cost. Here two ends leave the record’s catch where it was and move its worst case. The spread a merge sort does not have measured how much one sort’s count varies across random inputs, and the record’s length varies over two orders of magnitude across orderings. That variation is set by the order of the keys, and no amount of averaging over random inputs would show it.

The limits of these counts #

Bidirectional selection sort with the usual skipped second question. A variant that puts every key to both the minimum and the maximum has no holes and asks more questions. Its maximum chain would then be contiguous and the hole check would have nothing to guard. That variant was not measured.

Random keys from one shuffle a size, and eight more at 1,024. Across eight further shuffles of 1,024 keys, the pair of chains answers 98.9% to 99.2% of the repeats, the broken share runs from 0.045% to 0.058%, and the longest record from 21 to 25 links. The one-sided comparison at 1,024 uses the same first shuffle, so the 0.044% beside 0.040% is a comparison of single runs. Over the eight shuffles the two-ended broken share sits above the one-sided run’s 0.040% by up to half as much again. That is the same size, not the multiple of ten the prediction needed to reach whole per cent, and it does not depend on which shuffle is compared.

The attribution of a break to a swap is by the last swap that moved one of the two positions. When both positions were moved since the chain was recorded, the current extreme’s position is blamed. How often that convention decided the blame was not counted.

Answers are checked, not trusted. As in the one-sided record, the checks compare every answer with the keys and every answered question with the table of asked questions. They cost what the sort would cost without a record. The counts say what a record would save; they do not say it would be faster, which depends on what a comparison costs. The price of remembering an answer put that crossing at a comparison of about three word operations for the full table. For a record of a few dozen words it is lower, and it is still not zero. Counting instead of timing is why the numbers here are counts.

Still open: a record that knows when the input is sorted #

The two-ended record’s expensive inputs are the monotone ones, and a monotone input is also the one a sort should not be sorting at all. A scan that meets a run of new maxima, one at every position, is reading keys that are already in order. The record grows a link for each of them, and the sort compares each of them to find what the input’s order already said. The record that forgets on purpose found a record worth keeping only if it knew what to throw away. The two-ended record has a more specific choice: a run of consecutive links, each beaten by the key immediately after it, is an ordered stretch of the array, and it can be kept as one interval with a direction rather than as a link for every key.

The measurement that follows stores such runs as a single entry — a start, an end and the fact that every key in it beats the one before — and answers any question about two positions inside the run from their order alone. It asks how long the record then becomes on the four orderings and what share of repeats it still answers. The prediction is that sorted and reversed inputs fall from a link a key to one or two entries. Their repeats would all be answered, since every question on them is a question about two keys in one run. On random keys the record should be almost unchanged, since a random run of new extremes has expected length under two. Organ-pipe keys are the test. They consist of exactly two runs, and whether the compressed record answers the questions the one-pass chain lost there — the ones last asked before the previous pass — says whether a run is a better unit than a link, or merely a smaller one.