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

Insertion cutoff — where it appears

The subarray size below which a recursive sort switches to insertion sort, a threshold that trades comparisons against memory traffic. It trades comparisons against memory traffic, so its right value depends on which of the two the machine is actually charging for.

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

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

The sort the library ships

Every sorting algorithm measured on this site so far has one thing in common — none of them is what runs when a program calls sort. Python, Java, Rust and Android run Timsort; C++ runs introsort; Java's primitive sort is dual-pivot quicksort. Not one of the four was in this collection, and the reason it matters is that they are not algorithms in the sense the other essays use the word.

practice · Practice 1010010⁵minruncomparisonsshipped: 32randomnearly sortedTimsort, n = 8,192comparisons; rings mark the measured minimum

The threshold somebody chose

A minrun of 32. An insertion cutoff of 16. A gallop threshold of 7. A depth limit of twice the logarithm. Four numbers, in four real source files, none of which appears in any complexity analysis — and each of which decides more about what these algorithms do than the analysis does. Swept, they turn out not to be optima, and finding out what they are instead is the point.

practice · Count

Named alongside it

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

Comparison countCutoffIntrosortQuicksortThresholdTimsortComplexity classDepth limitGallopingJavaLibrary sortMerge policy

All concepts