A run answers what nobody asked

Two swaps a pass, and the stretches hold gave bidirectional selection sort a record of its past comparisons. The sort finds the smallest and the largest remaining key in each scan and places both. The record keeps the previous pass’s chain of minima and chain of maxima, each link a key that was the current extreme and the stretch of positions compared with it. The two chains answered 99% of the questions the sort repeated, and the swaps broke almost none of their answers. What the chains could not do was stay small. On reversed keys every key beats the minimum before it, so the minimum chain needs a link for every key. On sorted keys the maximum chain does the same. The record’s length is set by how often the scan meets a new extreme, and a monotone input makes that every time.

The essay’s closing section noticed what those links hold. A run of consecutive links, each beaten by the key immediately after it, says only that the keys in that stretch of the array are in order. It proposed keeping such a run as one entry, a start, an end and a direction, and answering any question about two positions inside it from their order alone. It predicted that sorted and reversed inputs would fall from a link a key to one or two entries, with every repeated question still answered, and that random keys, whose runs are short, would be almost unchanged. Organ-pipe keys, rising to the middle and falling after it, are exactly two runs, and whether a compressed record answers the questions the chains lost there would say whether a run is a better unit than a link, or only a smaller one.

What a record of runs keeps #

The record here is simpler than the proposal’s. It does not compress chains. It keeps, for each pair of neighbouring positions $p$ and $p+1$, what the sort has learned about their order: the key at $p+1$ is smaller, or larger, or nothing is known. It learns that from any comparison the sort makes, or answers, between two neighbouring positions, which a scan does constantly, since each scanned key is compared with a current extreme that is often the key just before it. It forgets it the moment a swap moves either position. A run is a maximal stretch of neighbouring pairs all known and all in the same direction. The keys in it are then monotone, and any question about two positions in the run — is the key at $j$ smaller than the key at $m$? — has an answer that follows from which of them comes first.

That is a different kind of answer from the chains’. A chain answers a question it has asked before: the key at $j$ was compared with the minimum at $m$ in the last pass, and neither has moved. A run answers by transitivity, and the question need never have been asked. The sort checks every answer from either record against the keys. It counts an answer to a question never asked separately from an answer to a repeat, since the first saves a comparison that no memory of past questions could have saved.

The record is run three ways: the previous pass’s two chains alone, as on the earlier page; the runs alone; and both, the chains consulted first for their own side’s question. With the runs switched off, the sort makes exactly the comparisons the earlier page counted on every ordering and size, which checks that nothing else changed.

Sorted keys, sorted in two comparisons a key #

On sorted keys, with runs kept beside the chains, the sort makes 2,045 comparisons at 1,024 keys and 8,189 at 4,096 — two a key — where the chains alone leave 263,167 and 4,198,399. The chains answer every question the sort repeats. On sorted keys that is half the questions, since each pass compares every remaining key with the maximum and all of those were asked the pass before. The other half are never repeats, because in each pass the minimum is compared with keys it has not met: the first key of the range stays the minimum, and the next pass starts one position further in with a new first key.

The runs answer those too, from the second pass on. In the first pass the scan compares each key with the current maximum, which is the key just before it, and so learns that every neighbouring pair is in order. On sorted input the swaps move nothing, since the minimum is already first and the maximum already last, so the run the first scan builds is never broken. Every later pass is answered entirely from it, the maximum’s questions by the chain as repeats and the minimum’s by the run as new questions. The sort makes the comparisons of one scan, about $2n$ of them, and none after.

Why the first scan still asks everything #

The first scan does not get the run’s help, and the order of the two questions is why. Counted pass by pass on 64 sorted keys, the first pass makes 125 comparisons — both questions for every key but the first — and every one of the other 31 passes makes none. When the scan reaches a key, it asks the minimum’s question first: is this key smaller than the first key of the range? Every pair up to the previous key is known by then, but the pair between the previous key and this one is not, because it is the maximum’s question, asked second, that relates them. So the run stops one position short of every key the minimum asks about, and the question is asked. Then the maximum’s question is asked too, and it closes the gap for the next key, which meets the same problem one position further on.

Asking the two questions the other way round would not help, since the maximum’s answer on a new key is what the minimum’s question would need, and asking the maximum first on sorted keys only changes which scan makes the first pass’s comparisons. What would help is knowing the neighbouring pair before the scan reaches it. When galloping pays found a merge that looks ahead, at a cost, on inputs where looking ahead finds long stretches, and a scan that related each key to the next before asking about either would be the same move. That is the closing question below.

That turns a selection sort into an adaptive one on sorted input, which no record of past questions could do. A record of stretches, not pairs found the one-sided sort asking no question twice on sorted keys, and so no memory could save it anything. It still made $n^2/2$ comparisons. A record that answers by transitivity makes it linear, because the questions it saves are the ones the sort was always going to ask for the first time.

Four orderings #

On organ-pipe keys the runs cut the comparisons by a quarter, from 344,265 with the chains to 256,924 with both; on random keys they save 0.2%; on reversed keys nothing, because the chains already answer everything. Reversed keys are the chains’ own best case. The minimum chain holds a link for every key, each question a repeat, and it answers every one, leaving 1,023 comparisons for the first scan. The runs reach the same count alone, with one run in place of 1,025 links. That half of the prediction holds exactly: one entry replaces a link a key, and every repeat is still answered.

Random keys are the other half. Alone, the runs save almost nothing: 516,862 comparisons at 1,024 keys against about 521,000 with no record at all. A random input’s neighbouring pairs alternate in direction, and a swap forgets two pairs each time it moves a key, so the runs of known order stay a few positions long. Beside the chains they add 434 answers out of a quarter of a million. The prediction said random keys would be almost unchanged, and they are; the chains carry everything there.

What each record holds #

At its largest, the record of runs holds 17 runs on random keys, 19 on organ-pipe keys and a single run on sorted and on reversed keys; the chains hold 21, 514 and 1,025 links. A run is three words, like a link, so on monotone inputs the record is a thousandth of the chains’ size and answers more. On random keys the two records are the same size and the runs answer almost nothing. The size of the run record follows the number of places where the known order changes direction, not the number of keys, and a monotone stretch of any length costs one entry.

The rel array behind the runs is not free. It holds two bits for each neighbouring pair of positions, 256 bytes at 1,024 keys, and it is read along the whole distance between two positions to decide whether they lie in one run. Stored as runs, with a start and an end, the lookup is a search among 19 entries, and the record is the 57 words the plate counts. The measurements here scan the array; a structure built for speed would keep the runs as intervals and split one when a swap lands inside it.

Organ-pipe keys, where the answers are new #

On organ-pipe keys the chains spare 32.0% of the sort’s comparisons at 1,024 keys, and chains with runs 49.2% — and 17.2% of all its comparisons are questions it had never asked, answered from two keys’ positions in a run. The organ pipe is two runs, rising to the middle and falling after it. The minimum’s scan meets the rising half and the maximum’s scan the falling one, and in each pass the two scans teach the record the order of the pairs they pass. The runs are then long, and most questions that cross one are new: the current extreme against a key further along its own half, which the sort would otherwise have asked for the first time.

The prediction asked whether a compressed record would answer the questions the chains lost on this input — the ones last asked before the previous pass, which no chain of one pass holds. It barely does. The chains and runs together answer 84.5% of the sort’s repeated questions at 1,024 keys, against the chains’ 84.3%. The runs’ contribution is elsewhere, in questions nobody asked. So a run is a better unit than a link, but not for the reason the section gave: it is a statement about the keys that answers questions not yet asked, where a link is a memory of an answer that can only be reused.

The share settles quickly with $n$: 16.3% at 128 keys, 17.2% at 1,024, 17.3% at 4,096. A run is a property of the input found the count of natural runs a better description of presortedness than any recipe for making presorted data. Here it is also the right description of what a record can learn. Two natural runs give the record two runs to keep, and the saving is set by how much of each scan falls inside one of them.

Random keys, where nothing is saved #

On random keys the record of runs changes the comparison count by 0.2% at 1,024 keys and 0.04% at 4,096. Nothing about a random input’s neighbours is worth remembering: each pair’s order is a coin flip, runs of the same direction are short, and each pass’s two swaps land at random positions and break what little the scan learned. The questions a sort asks twice found that half of selection sort’s comparisons on random keys are repeats, and the chains catch nearly all of those. What remains is new questions between keys the scan has not yet related, and on random keys no cheap record relates them.

That is the limit of what memory, of either kind, can do for a quadratic sort on random keys. The chains reduce it from about $n^2/2$ comparisons to about $n^2/4$. The runs add a transitive answer only where the input hands the scan long ordered stretches, and a random input hands it none.

What this changes about the strand #

The strand began with a table of every question a sort asks, and asked what share of it was worth keeping. The price of remembering an answer weighed the table against the comparisons it saved, and every record since has been a smaller table: a ring of rows, a chain of stretches, two chains. Each remembered answers. The run record is the first that infers them, and on the inputs where the chains were largest — sorted and reversed — it is the smallest record and answers the most.

The price of inference is exposure. A run’s answer is correct only if every pair in it is still in the order recorded, so a swap inside a run must break it. On sorted input no swap does, and on organ-pipe input the two swaps a pass land at the ends of the scanned range, near the ends of the runs. An input whose swaps landed in the middle of long runs would break them every pass, and the record would relearn them every pass, which the counts here never test. Counting instead of timing is why every saving is reported as comparisons. What a comparison costs against a lookup in the record decides whether any of it is worth doing.

The limits of these counts #

One shuffle and three structured orderings. Every random-key figure is one shuffle at each size, as in the earlier pages. The orderings are the earlier page’s four.

Distinct keys. Every input is a permutation. With equal keys a neighbouring pair can be equal, and a record of strict order would have to keep a third state; ties were not measured.

One order of questions. Every scan asks the minimum’s question before the maximum’s, as the earlier page’s sort does, and skips the maximum’s when a key beats the minimum. The first scan’s full cost on sorted keys follows from that order; a sort that asked the other way round would move the same cost onto reversed keys.

The record is scanned, not indexed. Whether two positions lie in one run is decided by reading the known order of every pair between them. The counts are of comparisons made, not of the work of that reading.

Still open: a sort that reads its runs before it scans #

On sorted keys the run record reaches two comparisons a key, and all of that is the first scan learning what a single pass over the input could have told it. A sort could make that pass first — one comparison between each pair of neighbours, $n - 1$ in all — and start its first scan with the whole record of runs already known. A request that reads the input first made the same move for a merge sort’s buffer and found the pass worth one comparison a key.

The measurement that follows gives the two-ended selection sort that pass and counts comparisons on the four orderings and on inputs of $k$ natural runs. The prediction is that sorted and reversed keys fall to about $n$ comparisons, the pass alone. Random keys should rise by the pass’s $n$, which the runs it finds cannot repay, and organ-pipe keys should fall further, since every question of the first scan would be answerable from the start. The number that decides whether the pass is worth making is the length of run at which the questions it lets the record answer outweigh the $n$ comparisons it costs, which is also the point at which a selection sort stops being the wrong sort to use.