Sorting without comparisons: count instead of compare

Merge sort, quick sort and heap sort take different routes, but they learn the order the same way: compare two values, act on the answer. However cleverly a sort picks its comparisons, if comparing is all it does, some list of a million values will cost it at least 18 million of them. That is a limit on comparing, not on any one algorithm.

Now put 100,000 exam scripts in order of mark, out of 100. No script needs comparing with another. Count how many got each mark, 101 tallies in all, and the tallies say where each mark goes: if 12 scripts got 0 and 30 got 1, the 2s come straight after the first 42. One pass to count and one to place is about 200,000 steps, where merge sort makes about 1.5 million comparisons. That is counting sort, and radix sort stretches it to bigger keys.

comparison sort

A sort that learns the order only by comparing two elements. Bubble, insertion, merge, quick and heap sort all are.

lower bound

The fewest steps every algorithm of a kind must take on its worst input.

key range k

Counting sort needs whole-number keys from 0 to k − 1, such as marks: k possible keys, whether or not they occur.

running total

Each count plus all the counts before it. Afterwards count[v] says how many keys are v or less.

stable

Equal keys come out in the order they went in. It matters for records, and radix sort depends on it.

digit and base

Radix sort writes each key as d digits in base b (base 10 has the digits 0 to 9) and sorts on one digit per pass.

Start with three different values. They can be in 3! = 6 orders, each needing different moves to put right. A comparison has two answers, so two comparisons end in at most 4 ways: two of the orders must end the same way, get the same moves, and one of them comes out wrong. Three comparisons end in up to 8 ways, which is enough.

In general, n different values can be in n! orders, and each comparison at best halves the orders still possible, so the worst case needs at least ⌈log₂ n!⌉ comparisons. That is a little under n log₂ n: about 18.5 million for a million values, where merge sort's worst case is about 19 million. In Comparison budget you sort hidden cards against this bound: 6 cards have 720 orders, so nobody can promise fewer than 10 comparisons.

The bound counts comparisons, so it covers only sorts that compare. Counting sort never does. It uses each key as an index into a row of counts: one step picks one of k cells, not one of two answers.

After the running totals, count[v] is how many values are v or less, so the values equal to v end just before position count[v]. Placing one at count[v] − 1 and lowering the count leaves the slot before it for the next equal value, so walking from the right puts the last of them last.

Count the work. One pass reads the n values to count them, the running totals visit the k counts, and a second pass places the n values: O(n + k) time, and O(n + k) memory for the count row and the output row B.

Before each placement, predict which output position the value goes to. Read its count in the count row: the value goes to count − 1, and the count drops by one for the next equal value. These seven values hold three 2s and two 4s.

The three 2s land in positions 4, 3 and 2, the last one first, so they leave in the order they arrived: 0 1 2 2 2 4 4.

Here is counting sort as a function, on five marks from 0 to 3, so k = 4. It prints the counts, then the running totals, then the sorted list. Two of the marks are 2, at indices 0 and 3.

def counting_sort(a, k):
    count = [0] * k
    for x in a:
        count[x] += 1
    print(*count)
    for v in range(1, k):
        count[v] += count[v - 1]
    print(*count)
    out = [0] * len(a)
    for i in range(len(a) - 1, -1, -1):
        count[a[i]] -= 1
        out[count[a[i]]] = a[i]
    return out

marks = [2, 0, 3, 2, 1]
result = counting_sort(marks, 4)
print(*result)

Walking from the right keeps equal keys in order. Walk from the left with the same two lines and the first 2 takes the last 2-slot: still sorted, but equal keys come out reversed, which undoes any earlier sort of the records by another field.

The trap is how big that price can get: the count row has a cell for every possible key, used or not.

Radix sort keeps the range small by sorting on one digit at a time. Each pass is a stable counting sort with just 10 counts, and the passes go from the ones digit up.

Each pass costs O(n + 10), one pass per digit of the largest key: d digits in base b cost O(d(n + b)) time and O(n + b) memory. Numbers below a billion take up to 9 passes over 10 counts, or 3 over 1,000 counts in base 1,000. With a fixed number of digits, as in 32-bit or 64-bit integers, radix sort is linear in n; fixed-length strings sort the same way, one character per pass.

• A comparison sort learns one yes or no per comparison, and n different values have n! orders, so its worst case needs at least ⌈log₂ n!⌉ comparisons, a little under n log₂ n.
• Counting sort never compares: count, take running totals, place from the end. O(n + k) time and memory, and stable.
• It pays for every possible key: ideal when k is no bigger than about n, hopeless for a few keys spread up to a billion.
• Radix sort runs a stable counting sort per digit, least significant first: d passes of O(n + b). Stability carries the lower digits' order into each pass.
• Next: bucket sort, which spreads values over buckets by range and sorts each, linear on average for evenly spread values. Practise where counting beats sorting with Same Letters, Different Order, Most Frequent Values and Group Anagrams, play the bound in Comparison budget, or open the counting sort and radix sort visualisers.