Counting Sort & Radix Sort: Linear-Time Sorting Explained

Counting sort and radix sort are non-comparison sorts: instead of comparing pairs of elements, they read the keys directly. By exploiting structure — that the keys are small integers — they break the O(n log n) lower bound that limits every comparison sort, sorting in linear time for the right kind of data.

Counting sort

Counting sort works when keys are integers in a known, small range [0, k]. It counts how many times each value appears, turns those counts into starting positions, and places each element directly where it belongs — no comparisons at all.

The idea in three steps:

Count occurrences of each key into a count array of size k + 1.
Prefix-sum the counts so count[v] becomes the number of elements ≤ v (the position just past where value v ends).
Place elements into the output. Iterating the input right to left and decrementing makes it stable.

std::vector<int> countingSort(const std::vector<int>& a, int k) {
    std::vector<int> count(k + 1, 0), out(a.size());
    for (int x : a) count[x]++;
    for (int v = 1; v <= k; v++) count[v] += count[v - 1]; // prefix sums
    for (int i = (int)a.size() - 1; i >= 0; i--)            // right-to-left = stable
        out[--count[a[i]]] = a[i];
    return out;
}

int[] countingSort(int[] a, int k) {
    int[] count = new int[k + 1];
    int[] out = new int[a.length];
    for (int x : a) count[x]++;
    for (int v = 1; v <= k; v++) count[v] += count[v - 1]; // prefix sums
    for (int i = a.length - 1; i >= 0; i--)                 // right-to-left = stable
        out[--count[a[i]]] = a[i];
    return out;
}

function countingSort(a, k) {
  const count = new Array(k + 1).fill(0);
  const out = new Array(a.length);
  for (const x of a) count[x]++;
  for (let v = 1; v <= k; v++) count[v] += count[v - 1]; // prefix sums
  for (let i = a.length - 1; i >= 0; i--)                 // right-to-left = stable
    out[--count[a[i]]] = a[i];
  return out;
}

def counting_sort(a, k):
    count = [0] * (k + 1)
    out = [0] * len(a)
    for x in a:
        count[x] += 1
    for v in range(1, k + 1):
        count[v] += count[v - 1]      # prefix sums
    for i in range(len(a) - 1, -1, -1):  # right-to-left = stable
        count[a[i]] -= 1
        out[count[a[i]]] = a[i]
    return out

Time: O(n + k). Space: O(n + k). Stable: yes (with the right-to-left placement).

Gotcha: Counting sort is only practical when k (the value range) is comparable to n. Sorting a handful of values in the range [0, 1,000,000,000] would allocate a billion-slot count array — disastrous. That range limit is exactly what radix sort removes.

Radix sort

Radix sort sorts integers (or fixed-length strings) digit by digit, from least significant digit (LSD) to most significant, using a stable counting sort on each digit. Because each pass is stable, earlier-sorted lower digits stay correctly ordered within ties on higher digits — so after the last digit the whole array is sorted.

Sorting [170, 45, 75, 90, 2, 802, 24, 66] by base-10 digits: first by ones, then tens, then hundreds; after the hundreds pass it is fully sorted.

void countingByDigit(std::vector<int>& a, int exp) {
    std::vector<int> out(a.size()), 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
        int d = (a[i] / exp) % 10;
        out[--count[d]] = a[i];
    }
    a = out;
}

void radixSort(std::vector<int>& a) {
    if (a.empty()) return;
    int mx = *std::max_element(a.begin(), a.end());
    for (int exp = 1; mx / exp > 0; exp *= 10) countingByDigit(a, exp);
}

void countingByDigit(int[] a, int exp) {
    int[] out = new int[a.length], count = new int[10];
    for (int x : a) count[(x / exp) % 10]++;
    for (int d = 1; d < 10; d++) count[d] += count[d - 1];
    for (int i = a.length - 1; i >= 0; i--) {             // stable
        int d = (a[i] / exp) % 10;
        out[--count[d]] = a[i];
    }
    System.arraycopy(out, 0, a, 0, a.length);
}

void radixSort(int[] a) {
    if (a.length == 0) return;
    int mx = a[0];
    for (int x : a) mx = Math.max(mx, x);
    for (int exp = 1; mx / exp > 0; exp *= 10) countingByDigit(a, exp);
}

function countingByDigit(a, exp) {
  const out = new Array(a.length), count = new Array(10).fill(0);
  for (const x of a) count[Math.floor(x / exp) % 10]++;
  for (let d = 1; d < 10; d++) count[d] += count[d - 1];
  for (let i = a.length - 1; i >= 0; i--) {              // stable
    const d = Math.floor(a[i] / exp) % 10;
    out[--count[d]] = a[i];
  }
  for (let i = 0; i < a.length; i++) a[i] = out[i];
}

function radixSort(a) {
  if (a.length === 0) return;
  const mx = Math.max(...a);
  for (let exp = 1; Math.floor(mx / exp) > 0; exp *= 10) countingByDigit(a, exp);
}

def counting_by_digit(a, exp):
    out = [0] * len(a)
    count = [0] * 10
    for x in a:
        count[(x // exp) % 10] += 1
    for d in range(1, 10):
        count[d] += count[d - 1]
    for i in range(len(a) - 1, -1, -1):    # stable
        d = (a[i] // exp) % 10
        count[d] -= 1
        out[count[d]] = a[i]
    a[:] = out

def radix_sort(a):
    if not a:
        return
    mx = max(a)
    exp = 1
    while mx // exp > 0:
        counting_by_digit(a, exp)
        exp *= 10

Time: O(d · (n + b)) where d is the number of digits and b the base (10 here) — effectively O(n) when d is small and constant. Space: O(n + b). Stable: yes.

Gotcha: The implementations above assume non-negative integers. To handle negatives, offset every value by -min before sorting (or sort negatives and non-negatives separately). Each digit pass must use a stable sort, or radix sort produces wrong results.

When to use them

Reach for counting/radix sort when keys are integers (or short fixed-length strings) in a bounded range — sorting ages, scores, ASCII characters, 32-bit IDs. For general data, or when the key range is huge or unknown, stick with the comparison sorts (merge, quick, heap). See where everything fits on the comparison page.

Next: Comparison of Sorting Algorithms.