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

Merge sort — where it appears

A sort that splits its input in half, sorts each half and merges the two sorted runs. Its comparisons stay within a narrow band for every input, it reads and writes sequentially, and its worst case is an ordering whose runs interleave at every merge.

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

048162432characters every key sharesoperations072,581145,162Character comparisonsRadix sort, characters readElement comparisonsone unit = one character comparisonelement comparisons constant at 3,955

The comparison that is not one comparison

Sorting 512 keys costs 3,955 comparisons whatever the keys are, and between 7,849 and 134,409 character examinations depending only on how much those keys have in common. The first number is the one every bound so far is stated in. The second is the one the machine pays, it grows without limit, and nothing here has ever counted it.

text · Symbol every orderthe named inputsmean0102030comparisonsInsertion sort7 to 28 · named inputs reach 28Merge sort12 to 17 · named inputs reach 16Heapsort21 to 29 · named inputs reach 27Quicksort, first-element pivot13 to 28 · named inputs reach 28Quicksort, median of three25 to 29 · named inputs reach 2540,320 orders of 8 distinct elements3 worst cases unnamed

A count over every input

Run five sorts on every one of the 40,320 orderings of eight elements and read off each one's best, mean and worst comparison count. Then mark where the inputs a benchmark generator names — sorted, reversed, nearly sorted, random, few unique — land. For merge sort, heapsort and quicksort with a median-of-three pivot, the worst case is an ordering none of them produces, and for the last of the three every named input lands on its best case.

counting · Count 40%60%80%100%8121624324864elements sortedshare of the known worst case the climbs reach, on averageInsertion sort · 20 of 24Merge sort · 24 of 24First-element quicksort · 0 of 24hollow: none reached it24 climbs a size · 100 swaps per elementworst cases known exactly

The worst case found by climbing

A search that swaps two elements at a time and keeps whatever does not lower the count finds the worst case of all five sorts at eight elements, where every answer can be checked. At sixty-four it finds merge sort's worst case every time and reaches 39% of first-element quicksort's — whose worst case is sorted input, the most famous bad input there is. Checking a search where the answer is known certifies it only there.

counting · Count 0.0010.010.11125102050fraction of positions reshuffled, pmean comparisons, in multiples of the mean on random inputFirst-element quicksort, 81.9×Median-of-three quicksort, 41.4×Insertion sort, 2.0×Merge sort, 1.0××: unshuffled2,048 elements · 12 shuffles a point1 = the mean on random input

A worst case ten positions wide

Sorted input costs first-element quicksort 2,096,128 comparisons on 2,048 elements, 82 times its average. Reshuffle about eleven of the 2,048 positions and the cost halves — and it takes about ten at 128 elements, and between ten and thirteen at every size between. Reversed input costs insertion sort twice its average, and reshuffling half the positions still leaves 71% of the work. A worst case is a place in the space of inputs, and the two famous ones are places of very different sizes.

counting · Count 0102030comparisons on one orderingfloor 16Insertion sort7 to 28 · mean 19.28Merge sort12 to 17 · mean 15.73Heapsort21 to 29 · mean 25.81First-element quicksort13 to 28 · mean 16.92Median-of-three quicksort25 to 29 · mean 26.30Batcher's network19 on all 40,32040,320 orders of 8, enumeratedfloor ⌈log₂ 8!⌉ = 16

The sort whose count has no distribution

Batcher's network makes nineteen comparisons on every one of the 40,320 orderings of eight elements — sorted, reversed, adversarial or random — because it decides which pairs to compare before it sees any of them. That is two above merge sort's worst case and four below heapsort's best. At 65,536 elements the same refusal to adapt costs 4.07 times merge sort's worst case, and it buys three things no adaptive sort has, one of which is a proof of correctness that takes 65,536 inputs instead of twenty trillion.

counting · Count 1101001,00010,00010⁵10⁶k, the elements the caller readscomparisonssort all, read kbuild a heap, pop kselect k, sort thoseincremental quicksortkeep the best k while scanningknockout tournamentdashed: the floorlabels at k = 1,00065,536 random distinct keysevery answer checked

The count of the part that was read

Handing back the smallest ten of 65,536 keys in order costs 965,656 comparisons by sorting them and 65,670 by a knockout tournament, against a floor of 65,526. Read to the last element, the same tournament makes exactly merge sort's 965,656 — it is merge sort, charged one element at a time. A sort's count has no term for how much of its answer anyone reads, and the two floors that do have one cannot simply be added.

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 length of the longer list, nshorter, m1234561234561floor 12floor 22floor 23floor 33floor 33floor 33floor 34floor 45floor 45floor 56floor 55floor 56floor 67floor 67floor 77floor 78floor 79floor 89floor 810floor 911floor 10the optimum is one above the floorthe floor is reachedevery cell solved exactly · m ≤ n ≤ 6large: the optimum · small: ⌈log₂ C(m+n, m)⌉

The floor a merge cannot reach

Merging two sorted lists of five keys each has 252 possible outcomes, so counting says eight comparisons might do. Solving the game says nine are needed, and on equal lengths the shortfall keeps growing, as half the logarithm of the length. Averaged over random inputs, though, the same count is missed by a tenth of a comparison. The counting floor is nearly exact on average and wrong in the worst case.

floors · Floor 0%25%50%75%Merge sort0.0% · 1.03× the floorQuicksort, random pivot0.0% · 1.16× the floorQuicksort, first-element pivot0.0% · 1.18× the floorMerge sort with an insertion cutoff0.0% · 1.31× the floorInsertion sort0.0% · 9.83× the floorShellsort9.8% · 1.31× the floorQuicksort, median-of-three15.4% · 1.18× the floorHeapsort26.2% · 1.45× the floorBubble sort49.2% · 9.83× the floorSelection sort59.9% · 7.77× the floorshare of comparisons whose answer was already implied256 elements, random orderlight: repeats nothing

The questions a sort asks twice

Selection sort makes 32,640 comparisons on 256 elements and 19,561 of them have answers it already holds. Remove every one and it still makes 7.8 times the information floor, because a question can be new and nearly worthless: insertion sort repeats nothing at all and removes 0.72 of a bit per comparison where merge sort removes 0.96. And bubble sort, less its repeats, makes exactly insertion sort's comparisons — at every size.

counting · Count

Named alongside it

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

Comparison countWorst caseExhaustive searchHeapInformation floorLower boundQuicksortAdversarial inputBenchmark inputCounting conventionCounterexampleMeasurement design

All concepts