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

Three-way partition — where it appears

A partition splitting into less, equal and greater, which turns a stream of duplicate keys from a quicksort's worst case into its best. It turns a stream of duplicate keys from a quicksort's worst case into its best, at the cost of one extra comparison per element.

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

the floor that applieslog₂(n!)Merge sort2.3×1,682Shellsort2.3×1,714Merge sort + cutoff2.6×1,938Heapsort4.2×3,101Quicksort, first6.6×4,887Quicksort, random7.2×5,291Quicksort, median-37.8×5,728Insertion sort18.5×13,644Bubble sort43.1×31,820Selection sort44.2×32,6408 distinct values, n = 256, seededthe two floors are 2.28× apart

The floor when the values repeat

log₂(n!) counts orderings of distinguishable things. Two hundred and fifty-six values drawn from eight distinct ones have 1,684 bits of permutation entropy and 739 bits of distinguishability, so the real floor is less than half the one every table quotes — and merge sort, which sits exactly on the quoted floor, is 2.3 times above the one that applies.

floors · Floor 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 Merge sortnone · 55% tiesMerge sort with an insertion cutoffnone · 47% tiesInsertion sortnone · 0% tiesBubble sortnone · 55% tiesShellsort2,014 · 71% tiesHeapsort2,403 · 32% tiesSelection sort1,209 · 24% tiesQuicksort, median-of-three pivot1,428 · 99% tiesequal pairs left out of the order they arrived in4,096 records, 8 distinct keysdark: the sorts that move them

The order equal keys keep

Four of the eight sorts here leave every pair of equal keys in the order it arrived in and four move between 1,209 and 2,403 pairs, and none of the four counts every plate here reports can tell them apart. Decorating each record with its arrival position makes any of them stable, for four thousand words and between 0.05 and 1.64 times its comparisons — a charge of 64% on Shellsort and a saving of 95% on quicksort, because the ties stability has to break are the ties a two-way partition chokes on.

counting · Count

Named alongside it

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

QuicksortComparison countCounting conventionPivotCounting sortCutoffDual-pivot quicksortEntropyHeapIntrosortJavaLower bound

All concepts