Card 01/ 11
Linear-Time Sorts: Reading the Key Instead of Comparing It
Counting, radix and bucket sort use a key's value to place it, and pay for that with assumptions about the keys.
Counting sort, radix sort and bucket sort are linear-time sorts: they can sort n items in time proportional to n, plus a term for the keys, because they place each item by reading its key's value rather than by comparing it with other items. This card maps the three, names the limit they get round, and names the assumption each one makes about the keys.
Every sort in the earlier topics of this section is a comparison sort: the only thing it learns about two items is which one is smaller. Any comparison sort needs about log₂(n!) comparisons in its worst case, which grows like n log₂ n, so merge sort and heapsort are as fast as such a sort can be. The proof belongs to Choosing a Sorting Algorithm, a later topic; the numbers are enough here. For 1,000 items, log₂(1000!) is about 8,529, against n log₂ n of about 9,966, and for seven items it is 12.3 against 19.7, so no comparison sort can promise to finish 1,000 items in fewer than 8,529 comparisons.
A linear-time sort escapes that limit by asking a different question. Instead of "is this key smaller than that one?", it asks "what is this key?" and uses the answer, a small integer, a digit, or a position within a range, as an index. Reading an index takes one step whatever n is. The price is an assumption: the key has to be something the sort can turn into an index cheaply, and when the assumption fails, the sort becomes slow, or needs more memory than the machine has.
| Algorithm | Reads from the key | Assumes | Time |
|---|---|---|---|
| Counting sort | The whole key, as an index into a count array | Integer keys in a range of k values, with k not much larger than n | O(n + k) |
| Radix sort | One digit at a time, least significant first | Keys with a fixed number d of digits in some base b | O(d · (n + b)) |
| Bucket sort | Which part of the range the key falls in | Keys spread evenly across a known range | O(n + b) on average, O(n²) at worst |
Read the Assumes column as the test for each sort. Counting sort keeps one counter per possible value, so a range of 101 temperatures costs 101 counters and a range of all 64-bit integers costs 2⁶⁴ of them. Radix sort cuts a wide key into a few narrow digits and runs a counting pass on each, so its cost depends on how many digits the key has. Bucket sort splits the range into intervals and hopes each interval holds a handful of items, which is true only when the keys are spread evenly.
Sorting letters into pigeonholes by house number works like a counting sort: the postman reads the number and drops the letter into its hole, without comparing two letters with each other. The analogy breaks at the wall. A sorting office has its pigeonholes built in, while a counting sort sizes its holes from the keys it is given, which is why a wide range of keys means a huge array of holes.
A hash table is not a linear-time sort, although it also turns a key into an index. A hash function scatters keys so that nearby keys land far apart, which is exactly what a sort must not do: walking a hash table's slots in order gives the keys in no useful order. The three sorts here use an index that grows with the key, so walking their counters, digits or buckets in order walks the keys in order.
The practical result is a question to ask before reaching for a comparison sort: what do the keys look like? Integers in a small range, fixed-width identifiers, and evenly spread measurements are each common, and each has a sort that beats n log n on it.
← → move through sections and cards