Merge sort, quicksort and heapsort learn about the order only by comparing two values, and any such sort needs about n log n comparisons in the worst case. But if the keys are small integers, or digits, you can use them directly as positions, and beat that bound.
To sort values by a key from 0 to 9 (say, one digit):
Going left to right and filling each key's slots from the front keeps values with equal keys in their original order. A sort with that property is called stable.
To sort numbers with several digits, counting-sort them by the ones digit, then by the tens, and so on, least significant digit first. Stability is what makes this work: when two numbers have the same tens digit, the tens pass leaves them in the order the ones pass put them in, which is the right order.
Each value's badge shows the digit of the current pass. Values move from the array into the output row below, then are copied back. Under the array, the table shows how many values have each digit, and the next free output slot for each digit.
| Counting sort | Radix sort | |
|---|---|---|
| Time | O(n + k) for keys 0 … k − 1 | O(d · (n + 10)) for d-digit numbers |
| Extra space | O(n + k) | O(n + 10) |
| Stable? | Yes, filled front to back | Yes |
| Catch | Only works on keys that break into small pieces: integers, fixed-length strings, dates. | |