Counting Sort & Radix Sort

Breaking the n log n barrier

Every sort that works by comparing two elements (bubble, merge, quick, heap…) needs at least about n log n comparisons in the worst case. That is a proven lower bound.

Counting sort and radix sort get around it by never comparing elements. They use the values themselves as array positions. This only works when the values are small whole numbers, or can be split into small digits.

Counting sort

For values between 0 and k:

1. Count how many times each value appears.
2. Turn the counts into positions with prefix sums: count[v] += count[v − 1]. Now count[v] is one past the last slot where v goes.
3. Walk the input from right to left. For each x, decrement count[x] and write x at that position.

Example with A = [2, 5, 3, 0, 2, 3, 0, 3] and k = 5:

So the two 0s go to positions 0–1, the 2s to 2–3, the 3s to 4–6 and the 5 to position 7. The output is [0, 0, 2, 2, 3, 3, 3, 5].

Walking from right to left makes counting sort stable: equal values stay in their original order.

Radix sort

What if the numbers go up to 999, or are 10-digit phone numbers? A count array that big is wasteful. Radix sort sorts by one digit at a time, using a stable counting sort (or 10 buckets) for each digit, starting from the least significant digit:

Why does it work? After pass 2, numbers with the same tens digit are still ordered by their ones digit, because the pass was stable. Each pass adds one more correctly sorted digit.

Code

def counting_sort(a, k):
    count = [0] * (k + 1)
    for x in a:
        count[x] += 1
    for v in range(1, k + 1):
        count[v] += count[v - 1]          # end position of each value
    out = [0] * len(a)
    for x in reversed(a):                 # right to left: stable
        count[x] -= 1
        out[count[x]] = x
    return out

def radix_sort(a):
    exp = 1
    while max(a) // exp > 0:              # one pass per digit
        buckets = [[] for _ in range(10)]
        for x in a:
            buckets[(x // exp) % 10].append(x)
        a = [x for b in buckets for x in b]
        exp *= 10
    return a

print(counting_sort([2, 5, 3, 0, 2, 3, 0, 3], 5))   # [0, 0, 2, 2, 3, 3, 3, 5]
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))  # [2, 24, 45, 66, 75, 90, 170, 802]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void radixSort(vector<int>& a) {
    int mx = *max_element(a.begin(), a.end());
    vector<int> out(a.size());
    for (int exp = 1; mx / exp > 0; exp *= 10) {
        int count[10] = {0};
        for (int x : a) count[(x / exp) % 10]++;
        for (int d = 1; d < 10; d++) count[d] += count[d - 1];
        for (int i = (int)a.size() - 1; i >= 0; i--)          // stable
            out[--count[(a[i] / exp) % 10]] = a[i];
        a = out;
    }
}

int main() {
    vector<int> a = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(a);
    for (int x : a) cout << x << " ";   // 2 24 45 66 75 90 170 802
}

When to use them

Real uses: sorting exam marks (0–100), ages, pixel values (0–255), IP addresses and suffix arrays in text search engines. Radix sort is also popular on GPUs, where it sorts millions of keys in parallel.

Common mistakes

• Using counting sort when the range is huge, for example values up to 10⁹. The count array would be enormous.
• Walking left to right in the placement step. The output is still sorted, but counting sort is no longer stable, and radix sort built on it breaks.
• Starting radix sort with the most significant digit and treating it like LSD. MSD radix sort needs recursion per bucket.
• Forgetting that numbers with fewer digits simply have a digit 0 in the higher places.