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.

6 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

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

Two pivots and what they cost

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