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

Record size — where it appears

How many bytes one element of a collection occupies, as distinct from how many elements there are. It decides how many fit in a cache line and how much a move costs, so it changes which of two algorithms is cheaper without changing either algorithm.

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

4 bytes32 bytes128 bytes512 bytesrecord:QuicksortMerge sortShellsortHeapsortInsertion sortSelection sortBubble sortQuicksortShellsortMerge sortHeapsortSelection sortInsertion sortBubble sortQuicksortShellsortMerge sortSelection sortHeapsortInsertion sortBubble sortSelection sortQuicksortShellsortMerge sortHeapsortInsertion sortBubble sort1234567n = 512, random input, key 8 bytesa read or a write moves the record; a comparison touches the key

The exchange rate nobody wrote down

Three earlier essays have said in passing that the ranking would change if the elements were large records. None of them computed it. Computed, selection sort goes from second-worst of seven at four bytes a record to best of seven at five hundred and twelve — and the crossover against each rival is a division that takes one line.

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 48163264128110entry width, bytescache lines a lookup readsentries inlinea line of tags in front8,192 slots, load 0.9, buckets of 8keys the table holds

A lookup that stops caring how wide an entry is

Buckets of eight entries aligned to a cache line read 1.20 lines a lookup when an entry is eight bytes and 19.25 when it is 128, because the bound was arithmetic about alignment and the arithmetic stops holding. Keeping one byte of each key's hash in a separate array and the entries in a parallel one reads 2.21 lines at every width from four bytes to sixty-four — and for a key the table does not hold, 2.05 against 31.98.

machine · Machine

Named alongside it

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

Comparison countSpace time tradeAlignmentCacheCache lineCost modelCounting conventionCrossoverCuckoo hashingData movementDesign parameterFalse-positive rate

All concepts