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

Radix sort — where it appears

A sort that distributes keys by one digit at a time rather than comparing them, and is finished after as many passes as the key has digits. It makes no comparisons at all, so the comparison sort's lower bound says nothing about it, and it needs keys that can be taken apart.

Named by 2 essays across 2 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 reads and writescache missesRadix sort, 8-bit digitsno comparisonsMerge sort965,752 comparisonsHeapsort1,895,405 comparisonsQuicksort, median-of-three1,187,435 comparisons65,536 keys of 32 bitsdark: the sort that compares nothing

The sort that makes none of them

Every count on this collection is a count of comparisons, swaps, reads or writes, and radix sort makes zero of the first. On 65,536 keys it moves five times less data than merge sort, misses the cache three times more, and sits 954,037 comparisons under the floor no comparison sort can go beneath — which is not an achievement, because the floor was never a statement about it.

counting · Count

Named alongside it

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

CacheCharacter comparisonComparison countComparison sortCost modelCounting conventionDistinguishing prefixInformation floorKey widthLower boundMeasurement designMerge sort

All concepts