Counting and Radix Sort: Choosing the Pass Count and the Digit Width

Sorting keys that are integers or fixed-length byte strings does not require comparing them. A pass that counts how many keys fall in each bucket, then computes running offsets, can place every key in its final position without a single comparison. Doing that once sorts keys in a small range. Doing it repeatedly on successive digits sorts keys in any range, and the choice of how many bits each digit holds is the main design decision.

Counting sort as a placement problem

Counting sort answers a narrower question than comparison sorting: given $n$ keys known to lie in $[0, k)$, produce the sorted sequence. Two passes suffice.

The first pass counts occurrences of each key, giving count[v] for each value $v$. The second pass turns the counts into starting offsets by prefix summation, then walks the input in order and places each key at its offset, incrementing the offset. The input order matters: because the walk goes front to back and offsets advance, equal keys land in the same relative order they had on input. The sort is stable by construction.

/* sort n keys in [0, k) into out; returns 0 on allocation failure */
int counting_sort(const unsigned *in, unsigned *out, size_t n, unsigned k)
{
    size_t *count = calloc((size_t)k + 1, sizeof *count);
    if (!count) return 0;
    for (size_t i = 0; i < n; i++) count[in[i]]++;
    size_t total = 0;
    for (unsigned v = 0; v <= k; v++) {   /* prefix sums become start offsets */
        size_t c = count[v];
        count[v] = total;
        total += c;
    }
    for (size_t i = 0; i < n; i++) out[count[in[i]]++] = in[i];
    free(count);
    return 1;
}

Cost is $\Theta(n + k)$ time and $\Theta(n + k)$ space for the input, output, and counter array together. Both terms matter. If $k$ is comparable to $n$, the sort is linear and beats any comparison sort. If $k$ is much larger than $n$, as when sorting a thousand 32-bit integers where $k$ is about four billion, the counter array dominates and the approach is useless without decomposition.

That ratio is the whole constraint. Counting sort is a good sort exactly when the key domain is small relative to the number of keys, and the technique below is how to make the domain small.

Splitting a wide key into digits

A $w$-bit key is a sequence of digits in base $2^r$, with $\lceil w/r \rceil$ digits. Sorting by the least significant digit first, with a stable sort at each digit, sorts the whole key. The argument is an induction on digit position: after pass $p$, the keys are sorted by their low $p$ digits. Pass $p+1$ sorts by digit $p+1$; since the sort is stable, keys with equal digit $p+1$ keep the order established by the previous passes, which is the order by low $p$ digits. After all digits, the keys are sorted by the full key.

Stability is not a convenience here; it is the mechanism. An unstable per-digit sort destroys the work of all previous passes. This is why counting sort, which is stable, is the usual inner sort, and why an in-place comparison sort such as quicksort, whose swaps reorder equal keys in no useful way, cannot serve as a digit pass.

/* LSD radix sort of n 32-bit keys; r bits per pass */
void radix_sort_u32(unsigned *a, unsigned *tmp, size_t n, unsigned r)
{
    const unsigned buckets = 1u << r;
    const unsigned mask = buckets - 1;
    unsigned *src = a, *dst = tmp;
    for (unsigned shift = 0; shift < 32; shift += r) {
        size_t count[256] = {0};          /* r <= 8 */
        for (size_t i = 0; i < n; i++) count[(src[i] >> shift) & mask]++;
        size_t total = 0;
        for (unsigned b = 0; b < buckets; b++) {
            size_t c = count[b];
            count[b] = total;
            total += c;
        }
        for (size_t i = 0; i < n; i++) dst[count[(src[i] >> shift) & mask]++] = src[i];
        unsigned *t = src; src = dst; dst = t;   /* ping-pong buffers */
    }
    if (src != a) memcpy(a, src, n * sizeof *a);
}

Note the double buffer. Each pass must read from one array and write to another, because the destination position of an element depends on counts gathered from the whole pass. Alternating the buffers avoids a copy per pass; one final copy handles the case where the pass count is odd.

The pass-width trade-off

With $w = 32$ and $r$ bits per pass, the number of passes is $\lceil 32/r \rceil$ and the counter array holds $2^r$ entries. Each pass costs one read and one write of every key, so total memory traffic is proportional to the pass count.

Bits per pass $r$	Passes for 32-bit keys	Counters	Counter memory (8-byte size_t)
4	8	16	128 bytes
8	4	256	2 KiB
11	3	2048	16 KiB
16	2	65536	512 KiB

Fewer passes means less traffic, so larger digits look strictly better. They are not, for two reasons.

The counter array must fit in cache for the counting and prefix-sum passes to be cheap. At 8 bits the counters occupy a few kilobytes and stay in L1 alongside the data stream; at 16 bits the counter array runs to half a megabyte, far beyond L1 and comparable to a typical L2, and each increment becomes a cache miss on a random index. The counting pass then degenerates into $n$ random accesses into a large array, which is the same pathology that makes a hash table with a working set larger than cache slow.

Second, the distribution of digit values matters. If keys cluster in a small part of the digit range, most counters are zero and the prefix-sum pass still walks all $2^r$ of them. With a 16-bit digit and keys that only use the low few thousand values, the prefix pass wastes most of its work.

The usual compromise is 8 bits per pass for byte-oriented keys, which gives four passes for 32 bits and keeps counters in cache. Implementations that know the key distribution sometimes use wider digits for the high-order passes, where the counter array is sparse anyway, or narrower ones where it is dense.

MSD radix and the recursion it enables

Least-significant-digit radix must complete every pass before any key is final. Most-significant-digit radix partitions by the top digit first, then recurses within each bucket on the next digit. After the first partition, the buckets are already in the correct relative order, so the recursion is on disjoint ranges and the result is complete when every range has one element or fewer.

The advantage is early termination: a bucket with a single key needs no further passes, and a bucket whose keys are all equal at the remaining digits needs none either. On keys with a shared prefix, such as timestamps in the same year or identifiers under a common namespace, the recursion skips most of the work. The disadvantage is that the recursion is data-dependent and the ranges become small and scattered, so the tight sequential streaming of LSD radix is lost.

MSD radix also has a base-case problem: small buckets are better handled by insertion sort than by another digit pass, because a pass costs a full scan plus counter setup regardless of bucket size. American-flag sort, a well-known MSD variant, uses a single in-place permutation pass per level and switches to insertion sort below a threshold.

Negative numbers and signed keys

Radix sort treats keys as unsigned bit patterns. Two’s-complement negatives sort after all positives if read as unsigned, which is the wrong order. The standard fix is to flip every key’s sign bit before sorting and to undo the flip on the output, which maps the signed order onto the unsigned one. The transformation preserves the relative order of equal keys, since equal keys receive equal transformations.

Floating-point keys need a different transform. For IEEE 754 doubles, the bit pattern of a positive value compares correctly as an unsigned integer, but negatives are reversed: a larger magnitude has a larger exponent field and therefore a larger unsigned pattern, while it should sort smaller. The standard mapping flips all bits of negative values and only the sign bit of non-negative values, which makes the unsigned comparison of the transformed patterns match the numeric order of the originals. The transform is a single XOR per key with a mask that differs by sign, and it must be inverted after sorting.

Where radix sort loses

Radix sort’s asymptotic advantage is real but narrow. It requires $n$ to be large relative to the key domain, it moves every key once per pass, and it needs a second buffer of $n$ keys. For 64-bit keys and 8-bit digits that is eight passes, each reading the whole array and writing it once, so sixteen passes over an array’s worth of data before the sort finishes. The practical result is that radix sort wins on large arrays of short keys or keys whose digits can be consumed a byte at a time, where the constant on each pass is a handful of instructions, and loses on long keys, small arrays, and anything where the counter array cannot stay resident.

Sorting strings of arbitrary length by radix requires either a fixed maximum length, wasting passes on short strings, or a variable-length scheme with per-length bookkeeping, which is why bytewise MSD schemes handle them better. The remaining limitations are the ones listed above: a key domain that must fit the counters, a full extra buffer, and a pass over the data for every digit rather than a comparison count that adapts to the input order.