Linear-time sorting

Merge sort & quicksort ended with a limit: a sort that learns about items only by comparing them needs about n log₂ n comparisons. The way around it is not to compare at all.

Suppose you sort 10,000 exam scores, each a whole number from 0 to 100. You don't need to compare scores with each other. Keep 101 counters, one per possible score, read each score once and add one to its counter, then write the scores back out in counter order. Each score was touched twice, whatever the order it arrived in.

Counting sort does exactly that. For values from 0 to k: count how many times each value appears, then walk the counts from 0 to k and write each value out as many times as it was counted.

The tally reads the n items once, and writing out walks all k + 1 counters: O(n + k) time and O(k) extra memory. When k is no bigger than about n, that is O(n).

The k in O(n + k) is the whole range of possible values, not how many values you have. Sorting 1,000 user IDs that run up to a billion would mean a billion counters, almost all of them zero. Counting sort suits small, dense ranges: ages, exam scores, letters, days of the month.

It also needs whole-number keys, or keys that map to them. Floating-point numbers or arbitrary strings have no small range to count over.

Writing values back from the counts works for plain numbers, but usually the numbers are keys of something bigger: people sorted by age, orders by day of the month. Then each record has to be moved, and equal keys should keep their order. The counts tell you where everything goes:

Because records are placed in the order they were read, records with equal keys keep their original order: this version of counting sort is stable. That property is what the next sort is built on.

Numbers up to a billion are too wide for counting sort, but each digit has only 10 values. Radix sort sorts by the ones digit, then by the tens digit, then the hundreds, each pass a stable distribution into 10 buckets.

Why does it work? Each pass is stable, so numbers with the same digit in this pass keep the order the earlier passes gave them, which is their order by the lower digits. After the last pass, numbers are ordered by their highest digit, ties broken by the next, and so on: fully sorted.

With d digits and base 10, radix sort makes d passes of O(n + 10): O(d × n) in all. For fixed-width keys such as 32-bit integers, phone numbers or zip codes, d is a constant and the sort is linear. Real implementations use a larger base, often 256 (one byte at a time), to cut the number of passes.

The h-index can't be larger than the number of papers, n, so any citation count above n can be treated as n. That caps the range at 0 … n, which makes counting sort's tally possible: count papers per citation count, then walk down from n adding up how many papers have at least h citations. O(n), no sorting.

Bucket sort splits a known range into n equal buckets, drops each value into its bucket, sorts each bucket with insertion sort, and reads the buckets in order. If the values are spread evenly across the range, each bucket holds about one value and the whole sort is O(n) on average.

If the values cluster, most of them land in a few buckets and the sorting inside those buckets dominates. Bucket sort is a bet on the input's distribution, not a guarantee.