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

Java — where it appears

A language whose standard library sorts with Timsort for objects and dual-pivot quicksort for primitives, both of them policies rather than algorithms. Both of its sorting policies are sets of thresholds and fallbacks rather than single algorithms, which is what makes a library sort worth measuring separately.

Named by 4 essays across 4 fields — 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 Dual-pivot116,836shipsIntrosort130,863shipspdqsort114,408shipsTimsort95,770shipsalgorithmcomparisonsrandom, n = 8,192comparisons, counted exactly

Two pivots and what they cost

Java changed its primitive sort in 2011 on the strength of an analysis showing dual-pivot quicksort does fewer comparisons than the classical one. It does. It also does nearly twice the swaps, and the analysis that decided the matter counted neither — it counted a weighted combination that had to be chosen before any conclusion could be drawn.

counting · Count column height = keys in that bucket · line = threshold of 8a well-spread hashlongest 44 → 4worst lookupthe low bits onlylongest 3131 → 5worst lookupevery key collideslongest 192192 → 8worst lookup192 keys, 256 buckets, seed 20260811threshold 8, 64 buckets shown

A bucket that becomes a tree

Java's HashMap converts a chained bucket into a red-black tree once it holds eight entries. The comment in the source computes the probability of that happening under a decent hash at about six in a hundred million, so the mechanism is written never to run. Under a hash that fails, the worst lookup falls from 192 comparisons to 8 — and the whole value of the tree is in a case its author does not control.

structures · Structure three-entry rule (as shipped, 2002–2015)1414101410314103141054+14+10+3+2+4final stack: 14, 10, 5, 414 is not > 10 + 5 — the invariant is brokenfour-entry rule (Java, after the proof)141410141031410333+14+10+3+2+4final stack: 33every triple satisfies the invariantrun lengths 14, 10, 3, 2, 4both outputs are correctly sorted

The invariant that was wrong for seven years

Timsort's merge policy is supposed to keep its run stack shallow, and the rule that enforces it inspects the top three entries. In 2015 a group of formal-methods researchers proved that the rule does not imply what it was believed to imply. Thirty-three elements are enough to break it, the array still comes out perfectly sorted, and the defect is in a structure that nothing about the output can show.

wrong · Structure

Named alongside it

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

TimsortCutoffIntrosortMerge policypdqsortPivotQuicksortSwapsThresholdChained hashingComparison countComplexity class

All concepts