Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Selection sort — where it appears

A sort that repeatedly scans the unsorted remainder for its smallest element and moves it into place. It makes the same number of comparisons on every input of a given size, and a large majority of them re-establish an order its earlier passes already settled.

Named by 15 essays across one field — each of them below, with the objects they name alongside it.

4 bytes32 bytes128 bytes512 bytesrecord:QuicksortMerge sortShellsortHeapsortInsertion sortSelection sortBubble sortQuicksortShellsortMerge sortHeapsortSelection sortInsertion sortBubble sortQuicksortShellsortMerge sortSelection sortHeapsortInsertion sortBubble sortSelection sortQuicksortShellsortMerge sortHeapsortInsertion sortBubble sort1234567n = 512, random input, key 8 bytesa read or a write moves the record; a comparison touches the key

The exchange rate nobody wrote down

Three earlier essays have said in passing that the ranking would change if the elements were large records. None of them computed it. Computed, selection sort goes from second-worst of seven at four bytes a record to best of seven at five hundred and twelve — and the crossover against each rival is a division that takes one line.

counting · Count 0%25%50%75%Merge sort0.0% · 1.03× the floorQuicksort, random pivot0.0% · 1.16× the floorQuicksort, first-element pivot0.0% · 1.18× the floorMerge sort with an insertion cutoff0.0% · 1.31× the floorInsertion sort0.0% · 9.83× the floorShellsort9.8% · 1.31× the floorQuicksort, median-of-three15.4% · 1.18× the floorHeapsort26.2% · 1.45× the floorBubble sort49.2% · 9.83× the floorSelection sort59.9% · 7.77× the floorshare of comparisons whose answer was already implied256 elements, random orderlight: repeats nothing

The questions a sort asks twice

Selection sort makes 32,640 comparisons on 256 elements and 19,561 of them have answers it already holds. Remove every one and it still makes 7.8 times the information floor, because a question can be new and nearly worthless: insertion sort repeats nothing at all and removes 0.72 of a bit per comparison where merge sort removes 0.96. And bubble sort, less its repeats, makes exactly insertion sort's comparisons — at every size.

counting · Count 32641282565121010010³10⁴elements sortedword operations a comparison must cost to break evenSelection sort, pairsSelection sort, closureBubble sort, pairsBubble sort, closureHeapsort, pairsHeapsort, closureQuicksort, median-of-three, pairsQuicksort, median-of-three, closuresolid: pairs asked · dashed: everything impliedrandom input · counted exactly

The price of remembering an answer

Give selection sort a table of the pairs it has already compared and it makes 16,805 comparisons on 256 elements instead of 32,640. The table pays for itself once a comparison costs more than 3.1 word operations, and that price stays near three at every size measured. Give it the full closure of everything its answers imply and it makes 13,079. The closure pays only past 425 operations a comparison at that size, and past 1,659 at twice the size. The cheap memory is worth having on long keys. The complete one is worth having almost nowhere.

counting · Count 1,00010010³10⁴10⁵10⁶keys sortedcache missesno recorda cache of 1,024 pairsthe table, written twicethe table, by ordered pairselection sort, 512 lines of 64 bytesexact LRU

The record measured where it would run

A table of every pair selection sort has compared saves half its comparisons at 1,024 keys, and priced in word operations it was the better record at every size. Replayed through a 32 KB cache it misses 477,824 times to save 258,290 comparisons — nearly two misses for every comparison it removes — while a cache of 1,024 pairs misses 192. The table's size is not the problem. Its layout is: it looks up and writes each question at [key][minimum], a new row every time. Indexed by the ordered pair instead, the same bits miss 3,079 times, and that repair works only for a sort whose smaller operand stays put.

counting · Count 1248163264rows in the ringshare of the table's skipped comparisons0%25%50%75%100%256 keys1,024 keys2,048 keysselection sort, random keysticks: expected minima a pass

A record the size of a pass's minima

Selection sort's table of every pair it has compared is 256 KB at 1,024 keys, and indexed by the ordered pair it lives almost entirely in the rows of the current minima. Keep only those rows — a ring of r rows, the least recently used given up — and 12 rows, 3 KB, catch 99% of the comparisons the whole table skips, with no misses beyond the first touch of each row. The ring beats the cache of 1,024 pairs on both axes at once. The rows it needs grow with the logarithm of the input, a few more than the minima one pass passes through, and which row it gives up matters as much as how many it has.

counting · Count 1282565121,0242,0484,096keys sorted, ntable's skips caught94%96%98%100%the chain of the last passa ring of twelve rowsrandom keys, every answer checkedring: the earlier record, LRU

A record of stretches, not pairs

Selection sort asks many of its comparisons again, and a record of past answers can skip them. A table of every pair skips them all in 256 KB at 1,024 keys, and a ring of the recent minima's rows in 3 KB. The questions a pass repeats have more structure than rows record: each minimum of the previous pass was compared with one contiguous stretch of positions. Kept as a list of stretches — each minimum's position, where its stretch began, and where the key that beat it stood — the previous pass's chain answers 99.3% of what the table would, in 312 bytes. The failure predicted for it, a key the swap moves into a stretch, costs 0.04%. What the chain cannot do is stay small on every input: on reversed keys it needs a link for every key.

counting · Count 1282565121,0242,0484,096keys sorted, nrepeats answered94%96%98%100%minimum chain, its own repeatsmaximum chain, its own repeatsone-sided sort's chainrandom keys, every answer checkedeach share of its own side's repeats

Two swaps a pass, and the stretches hold

Bidirectional selection sort finds the smallest and the largest key in one scan and places both, so a record of its past answers has to keep two chains, and each pass makes two swaps that land where the other chain reaches. The prediction was that the second swap would break stretches at a rate of whole per cent. It does not. Each chain answers its own side's repeats as the one-sided chain does — 99.1% and 99.2% at 1,024 keys — and a swap spoils about a tenth of a question whichever sort makes it, so the broken share falls as 1/n for both. What the second chain changes is the input that makes a record long: sorted keys, which the one-sided sort never repeats a question on, cost the two-ended record a link a key.

counting · Count 1282565121,0242,0484,09610³10⁴10⁵10⁶keys sorted, ncomparisons madethe two chainschains and runssorted keys, every answer checkedruns: adjacent positions of known order

A run answers what nobody asked

Bidirectional selection sort remembers its past comparisons in two chains, and on sorted or reversed keys the chains need a link for every key. Keeping instead what is known about adjacent positions — which of each neighbouring pair is larger, forgotten when a swap moves either — turns a monotone stretch into a single run with a direction. On reversed keys one run replaces 1,025 links. On sorted keys the run does more than remember: it answers 260,610 questions the sort had never asked, from two keys' positions alone, and the sort makes 2,045 comparisons at 1,024 keys where the chains leave 263,167. On organ-pipe keys it cuts a quarter of the comparisons; on random keys, nothing.

counting · Count chains and runsthe same, after a pass over neighboursrandom261,452261,688reversed1,0231,023organ-pipe256,924213,148sorted2,0451,0231,024 keys, the pass's comparisons includedevery answer checked against the keys

A pass repaid by the scans after it

Give the two-ended selection sort one pass between neighbours before it starts, n − 1 comparisons, and sorted and reversed keys cost exactly that pass. The pass was predicted to be repaid in the first scan, and almost none of it is. On organ-pipe keys it saves 43,776 comparisons at 1,024 keys, 97% of them in the scans after the first. On random keys it costs 236, not 1,023, because later scans use the short runs it found. It breaks even on runs of four keys at every size — and the sort stays quadratic on every input that is not one run.

counting · Count 00.500123458shortest run the record keeps, in keyscomparisons a key the pass addsthe pass's own cost, one comparison a key1,024 keys4,096 keys256 keysrandom keys, chains and runs, every answer checkedpass included

The runs too short to drop

A pass between neighbours leaves the two-ended selection sort a record of 674 runs on 1,024 random keys, and the scans after it use them to repay three quarters of the pass. Keeping only runs of three keys or more was predicted to cut the record by two thirds and give back under a tenth of what it repaid. It cuts the record by 63%, and gives back 69%: runs of two keys answer half of everything the record answers, because three quarters of its answers are about two neighbouring positions — the question a scan asks about the key beside the extreme it has just found. The record's cost was never in its short runs. It was in writing each run as three words: every neighbouring pair at two bits a pair is 64 words, a thirty-second of the run list, and keeps all of them.

counting · Count keys in each sorted run of the inputreads spent per comparison saved (log scale)1101001,00010,000416642561,024256 keys1,024 keys4,096 keyssolid: two bits a pair · faint: run listreads per comparison saved

What it costs to consult two bits a pair

The two-ended selection sort's record of adjacent order can be kept as two bits a neighbouring pair or as a list of runs, and the page that compared them counted both as free to read. Priced, the bits read 1.09 words a question on 1,024 random keys — under the two predicted — and a binary search of the run list takes 8.8 steps, because the pass leaves 503 runs to search. The run list was predicted to win from runs of sixteen keys; it wins only from runs of 512. Both prices are small and neither is small enough. Asked every question the sort makes, the bits spend 201 word reads for every comparison the record saves on runs of four keys, 764 at 4,096 keys, where a table of compared pairs broke even at three. The record repays its reading only on long runs, and the pass that finds them is also the cheapest place to decide whether to consult at all.

counting · Count 0124816keys in each sorted run of the inputreads a question: words, or probes of the list48163264128256512sortedone word: the word that holds the first pairrun list, probestwo bits a pair, wordsbehind the filter, words1,024 keys, a pass firstsorted array cut at 24

A filter that reads the word it saves

A selection sort's record of adjacent order, two bits a neighbouring pair, costs 1.09 word reads a question and spends 201 of them for every comparison it saves on 1,024 keys in short runs, because it is asked everything and answers almost nothing. A filter bit beside each pair, set only where a run could start, was predicted to turn away three quarters of the questions and cut that price to under sixty. It turns away two thirds and cuts the price to 185. The questions it turns away were already refused in the first word, the filter is read in that same word, and one read a question is a floor no filter can go under.

counting · Count keys sortedword reads for each comparison saved (log scale)141664256break-even of a pair table2561,0244,096runs of 4runs of 16runs of 64dashed: without registersa pass firstlogarithmic scale

A run end kept in a register

A selection sort's record of adjacent order spends about a word read on every question it is asked, and on short runs it is asked 184 questions for every comparison it saves, so no filter read in that word can make it pay. Every question starts from one of the sort's two current extremes, and what the record can say about all of them is one number: where the run from that extreme ends. Kept in a register beside each extreme and refreshed only when it changes, that number cuts the reading to a forty-fifth on 1,024 keys in runs of four, and the price of a saved comparison from 201 word reads to 4.5, where it stops growing with the input.

counting · Count keys in each sorted run of the inputwords read a question (log scale)0.111048163264128256512sortedregisterskept past a breakanswering from insidetwo bits a pair, plain1,024 keys, a pass firstlogarithmic scale

A register dropped by what it already knew

Two registers beside a two-ended selection sort's extremes cut the reading of its record of adjacent order to a forty-fifth on short runs, and made it worse than reading the record plainly on long ones: 53.5 words a question on a sorted array of 1,024 keys against 22.1. The swaps were blamed, and the proposed repair kept the part of a broken run beyond the break as a register of its own. It changes the reading by under 1% anywhere. On the sorted array the survivors are kept 523,775 times and asked 1,022 times, and the sort makes no swap at all: every one of the 263,167 relearning drops there is a pair the record already held, rewritten at the same value by a neighbour's question that the previous scan's chains answered. The swap never broke the register. Learning what it already knew did.

counting · Count keys in each sorted run of the inputreads a question (log scale)0.111048163264128256512sortedregisterstwo bits a pair, plainrun list's searchkept through a relearning1,024 keys, a pass firstlogarithmic scale

A register kept through a confirmation

Two registers beside a two-ended selection sort's extremes, holding where the run of known order from each one ends, read 53.5 words a question on a sorted array of 1,024 keys, more than reading the record plainly — because 263,167 times a neighbour's question, answered by the previous scan's chains, rewrote a pair at the value it already held, and each rewrite dropped a register. Kept through such a confirmation and dropped only when a pair is forgotten or turns round, the registers read 0.347 words a question on that array, a 154th, and 0.345 on 4,096 keys: the reading stops growing with n. They become the cheapest record at every run length, 49 to 73 times under the next on runs and 5.75 times under the run list's search on the sorted array, and the price of a saved comparison now falls as runs lengthen, from 3.97 word reads at runs of four to 0.35. The dearest saving is now the short run's, and it is still above the 3.1 at which a table of compared pairs breaks even.

counting · Count

Named alongside it

The objects these essays reach for when they reach for this one.

Comparison countSpace time tradePredictionNatural runMeasured countBit vectorTransitivityLocalityMemoisationWorking setCost modelHonest limit

All concepts