Generator

Comparisons on random input, n = 8,192

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
Comparisons on random input, n = 8,1924 of these are what a standard library actually runs. Timsort is lowest at 95,770 and Introsort highest at 130,863, a factor of 1.37. Changing the counter changes the order, which is the reason this field measures four of them and refuses to name a winner.Timsort95,770shipsIntrosort130,863shipspdqsort114,408shipsDual-pivot116,836shipsalgorithmcomparisonsrandom, n = 8,192comparisons, counted exactly

Comparisons on random input, n = 8,192

4 of these are what a standard library actually runs. Timsort is lowest at 95,770 and Introsort highest at 130,863, a factor of 1.37. Changing the counter changes the order, which is the reason this field measures four of them and refuses to name a winner.

Drawn at 700 × 216, wide on the page. Everything above is what library-scoreboard returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

17 essays call library-scoreboard. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

Timsort95,770shipsIntrosort130,863shipspdqsort114,408shipsDual-pivot116,836shipsMerge sort96,145textbookHeapsort187,796textbookQuicksort, median-3119,098textbookalgorithmcomparisonsrandom, n = 8,192comparisons, counted exactly What the libraries do

The sort the library ships

11010010³10⁴10⁵10⁶10⁷natural runs r in the inputcomparisonsn / minrun = 256TimsortMerge sortInsertionn + n log₂ rn = 8,192, runs built exactlycomparisons, counted exactly What the libraries do

A run is a property of the input

dark: with galloping · pale: with the mode removednearly sorted33,95221,373 jumped−37.7%few distinct values57,91241,178 jumped−36.9%random95,7702 jumped+0.0%n = 8,192, MIN_GALLOP = 7comparisons, counted exactly What the libraries do

When galloping pays

algorithmspread of count ⁄ f(n) — 1.0 is exactTimsortPython, Java objects, Rust, Android1.176nIntrosortC++ std::sort1.104n log nPattern-defeating quicksortRust unstable sort, Boost, libstdc++ 141.155nDual-pivot quicksortJava Arrays.sort, primitives1.624no class grantedtolerance 1.6fitted n = 256–16,384comparisons, counted exactly What the libraries do

The pattern that defeats the pattern

1010010⁵minruncomparisonsshipped: 32randomnearly sortedTimsort, n = 8,192comparisons; rings mark the measured minimum What the libraries do

The threshold somebody chose

050100150elements of buffer obtained — the request, then each halving the allocator falls back toper key sorted32,7688,1922,0485121283282nonemovescomparisonsn = 65,536, distinct keys, random ordera swap counts as three moves What the libraries do

A guarantee that depends on an allocation

Dual-pivot116,836shipsIntrosort130,863shipspdqsort114,408shipsTimsort95,770shipsalgorithmcomparisonsrandom, n = 8,192comparisons, counted exactly Counting

Two pivots and what they cost

15202530buffer, as a share of the inputelement moves a key0n/4n/23n/4nn/16n/8n/4n/2nthe request65,536 keysline: the lower hull What the libraries do

The request no price of memory would make

01020natural runs in the inputelement moves a key12416642561,0244,096randomlibrary, half the inputlibrary, a quarterout of place, the wholeruns found first65,536 keys, runs of random lengtha swap counts three moves What the libraries do

A request that reads the input first

1/21/41/81/161/641/25625102050buffer, share of the inputmoves a keyfour runs, runs read firstfour runs, the libraryrandom keys, runs read firstrandom keys, the library65,536 keys, schedule smallest-firstdashed: random keys What the libraries do

The buffer a schedule cannot bend

1/41/81/161/641/2561/10240.10.3131030buffer, share of the inputmoves a keythe libraryruns read, no trimruns read, trimmedsixteen batches, 5% overlap, 65,536 keysschedule smallest-first What the libraries do

The skip the split already made

125102050buffer, as a share of the inputwrites ÷ the floor1/41/161/641/2561/1024sixteen batches, 5% overlapa random tenth appendeda late tenth appendedfour runssixteen runsrandom keys65,536 keys, trimmed sortone: the floor itself What the libraries do

The moves no stable sort can skip

125102050100buffer, as a share of the filemoves a key of the file (log scale)1/41/161/641/2561/10241/4096pieces by insertionpieces by mergingmerge sort, whole tail65,536 keys, a late tenth from the top fifthmoves counted, sorted checked What the libraries do

Pieces that fit the buffer

1248163264buffer, as a share of the filemoves a key of the file (log scale)1/161/321/641/1281/2561/10241/4096pieces straight into the headthe proposed rulepieces merged to one firstmerge sort, whole file65,536 keys, a late tenth from the top fifthmoves counted, sorted checked What the libraries do

How many pieces the head can afford

buffer, as a share of the filemoves a key of the file (log scale)12481632641/161/321/641/1281/2561/10241/4096wrong endpieces straight in, paidpieces straight in, pricedmerged to one first, paidmerged to one first, priced65,536 keys, a late tenth from the top fifthdashed: priced in advance What the libraries do

The rotation that could be priced

buffer, as a share of the filemoves a key of the file (log scale)12481632641/161/321/641/1281/2561/10241/4096pieces straight in, paidpieces straight in, pricedmerged to one first, paidmerged to one first, priced65,536 keys, a late tenth from the top fifthdashed: priced in advance What the libraries do

The head each piece will meet

reach 0.1reach 0.2reach 0.4reach 0.7reach 1buffer 1/128buffer 1/256buffer 1/10240/40/55/7 · best 60/45/57/74/45/57/74/45/57/74/45/57/7cells: rounds chosen / rounds possible · dark: none · light: all · marked: a missfifteen settingsthe priced rule's choice What the libraries do

Every number of rounds, priced

The library, page 2 of 5 — where library-scoreboard sits