Chapter 20 of 65

Counting Sort & Radix Sort

On this page

Imagine a teacher has 500 answer sheets, and every student scored a whole number between 0 and 10. She wants the sheets in order of marks.

She doesn't need to compare sheets with each other at all. She just makes 11 piles, one for each possible mark, drops every sheet into its pile, and then stacks the piles from 0 to 10.

Pile 0: ...   Pile 1: ...   Pile 2: ...   ...   Pile 10: ...

Stack them in order → sorted!

That's the idea behind Counting Sort. And when the numbers are too big for one pile per value, we can sort them one digit at a time using the same trick. That's Radix Sort.

Every algorithm we've seen so far (Bubble, Selection, Insertion, Merge and Quick Sort) works by comparing two elements. Counting Sort and Radix Sort are different: they never compare elements. They use the values themselves as array indexes.


Why Not Just Use Comparisons?

There is a famous result about comparison-based sorting:

Any sorting algorithm that only compares pairs of elements needs Ω(n log n) comparisons in the worst case.

The intuition: n elements can be arranged in n! different orders, and each comparison has only two outcomes (yes or no). To tell all n! orders apart, you need at least log₂(n!) comparisons, which grows like n log n.

So Merge Sort and Quick Sort (on average) are already as good as comparison sorting can get.

To go faster, we have to stop comparing and use extra information about the data. Counting Sort and Radix Sort do exactly that, but they only work for certain kinds of keys, usually integers in a known range.


Counting Sort: The Simple Version

Let's sort:

[4, 2, 2, 8, 3, 3, 1]

Step 1: Count each value

The largest value is 8, so we create a count array of size 9 (indexes 0 to 8). Then for each element, we increment count[element].

value:  0  1  2  3  4  5  6  7  8
count: [0, 1, 2, 2, 1, 0, 0, 0, 1]

This says: one 1, two 2s, two 3s, one 4 and one 8.

Step 2: Write the values back in order

Walk through count from left to right and write each value count[v] times:

[1, 2, 2, 3, 3, 4, 8]

Here's the code:

import java.util.Arrays;

class Main {

    static void countingSortSimple(int[] arr) {

        int max = arr[0];
        for (int x : arr) {
            max = Math.max(max, x);
        }

        // Step 1: count how many times each value appears
        int[] count = new int[max + 1];
        for (int x : arr) {
            count[x]++;
        }

        System.out.println("Count:  " + Arrays.toString(count));

        // Step 2: write each value back, count[v] times
        int index = 0;
        for (int v = 0; v <= max; v++) {
            while (count[v] > 0) {
                arr[index++] = v;
                count[v]--;
            }
        }
    }

    public static void main(String[] args) {

        int[] arr = {4, 2, 2, 8, 3, 3, 1};

        countingSortSimple(arr);

        System.out.println("Sorted: " + Arrays.toString(arr));
    }
}

Output:

Count:  [0, 1, 2, 2, 1, 0, 0, 0, 1]
Sorted: [1, 2, 2, 3, 3, 4, 8]

This version works perfectly for plain integers. But it rebuilds the values from the counts. If each number were attached to some other data (like a student's name), that data would be lost. For that, we need the stable version.


Counting Sort: The Stable Version

The stable version figures out the exact output position of each element and moves the original elements there. It has three steps.

Step 1: Count frequencies

value:  0  1  2  3  4  5  6  7  8
count: [0, 1, 2, 2, 1, 0, 0, 0, 1]

Step 2: Prefix sums

Replace each count with the running total. You may recognise this as the prefix-sum idea, which has its own chapter later.

count[v] = count[v] + count[v - 1]

value:   0  1  2  3  4  5  6  7  8
prefix: [0, 1, 3, 5, 6, 6, 6, 6, 7]

Now prefix[v] means "how many elements are ≤ v". For example, prefix[3] = 5: five elements are ≤ 3, so the last 3 belongs at index 4 (the fifth slot).

Step 3: Place elements, scanning from the right

For each element v, from the end of the input to the start: decrease prefix[v] by one, then put v at that index.

input: [4, 2, 2, 8, 3, 3, 1]
index:  0  1  2  3  4  5  6

i = 6: v = 1 → prefix[1]: 1 → 0, output[0] = 1
i = 5: v = 3 → prefix[3]: 5 → 4, output[4] = 3   (second 3)
i = 4: v = 3 → prefix[3]: 4 → 3, output[3] = 3   (first 3)
i = 3: v = 8 → prefix[8]: 7 → 6, output[6] = 8
i = 2: v = 2 → prefix[2]: 3 → 2, output[2] = 2   (second 2)
i = 1: v = 2 → prefix[2]: 2 → 1, output[1] = 2   (first 2)
i = 0: v = 4 → prefix[4]: 6 → 5, output[5] = 4

output: [1, 2, 2, 3, 3, 4, 8]

Look at the two 3s. The second 3 (index 5) was placed at output index 4, and the first 3 (index 4) was placed at output index 3. Their original order is preserved. That is what makes this version stable.

import java.util.Arrays;

class Main {

    static int[] countingSort(int[] arr) {

        int n = arr.length;

        int max = arr[0];
        for (int x : arr) {
            max = Math.max(max, x);
        }

        // Step 1: frequencies
        int[] count = new int[max + 1];
        for (int x : arr) {
            count[x]++;
        }
        System.out.println("Count:  " + Arrays.toString(count));

        // Step 2: prefix sums -> count[v] = number of elements <= v
        for (int v = 1; v <= max; v++) {
            count[v] += count[v - 1];
        }
        System.out.println("Prefix: " + Arrays.toString(count));

        // Step 3: place elements, scanning from the RIGHT for stability
        int[] output = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            int v = arr[i];
            count[v]--;
            output[count[v]] = v;
        }

        return output;
    }

    public static void main(String[] args) {

        int[] arr = {4, 2, 2, 8, 3, 3, 1};

        int[] sorted = countingSort(arr);

        System.out.println("Sorted: " + Arrays.toString(sorted));
    }
}

Output:

Count:  [0, 1, 2, 2, 1, 0, 0, 0, 1]
Prefix: [0, 1, 3, 5, 6, 6, 6, 6, 7]
Sorted: [1, 2, 2, 3, 3, 4, 8]

Why scan from the right? Each value's slots are filled from the last slot backward. Scanning the input from the right means the last occurrence gets the last slot and the first occurrence gets the first slot. If you scan from the left with this code, equal elements come out reversed and the sort is no longer stable.


Handling Negative Numbers

Array indexes can't be negative, so count[-5] is impossible. The fix is to shift every value by the minimum:

index = value - min

min = -5:   -5 → 0,   -2 → 3,   0 → 5,   3 → 8
import java.util.Arrays;

class Main {

    static int[] countingSort(int[] arr) {

        int min = arr[0], max = arr[0];
        for (int x : arr) {
            min = Math.min(min, x);
            max = Math.max(max, x);
        }

        int k = max - min + 1;          // size of the value range
        int[] count = new int[k];

        for (int x : arr) {
            count[x - min]++;           // shift so min maps to index 0
        }

        for (int v = 1; v < k; v++) {
            count[v] += count[v - 1];
        }

        int[] output = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int idx = arr[i] - min;
            count[idx]--;
            output[count[idx]] = arr[i];
        }

        return output;
    }

    public static void main(String[] args) {

        int[] arr = {-5, 3, 0, -2, 3, -5, 1};

        System.out.println(Arrays.toString(countingSort(arr)));
    }
}

Output:

[-5, -5, -2, 0, 1, 3, 3]

Using max - min + 1 as the size also saves memory when values don't start near 0. For values between 1000 and 1010, we need just 11 counters, not 1011.


Counting Sort Complexity

Let n be the number of elements and k the size of the value range (max - min + 1).

Find min/max   → O(n)
Count          → O(n)
Prefix sums    → O(k)
Place elements → O(n)

Time  → O(n + k)
Space → O(n + k)   (output array + count array)

The time is the same in the best, average and worst case, because the algorithm does the same steps no matter how the input is ordered.

When k is small (about the same size as n or smaller), this is linear time, faster than any comparison sort.

When Counting Sort Is a Bad Idea

If the range is huge, k dominates:

arr = [5, 1000000000, 3]

n = 3, but k ≈ 1,000,000,000
→ a count array of a billion ints (about 4 GB)

Sorting three numbers would need gigabytes of memory. In such cases, use a comparison sort, or Radix Sort.

Counting Sort also doesn't work directly for double values or arbitrary objects, because they can't be used as array indexes.


Radix Sort: Sorting Digit by Digit

What if we want to sort numbers up to a billion? One counter per value is too many. But each number has at most 10 decimal digits, and each digit is only 0 to 9.

Radix Sort sorts the numbers one digit at a time, using a stable Counting Sort on that digit.

LSD Radix Sort sorts integers by processing their digits from the least significant (ones) to the most significant, using a stable sort for each digit.

"Radix" means the base of the number system. For decimal numbers, the radix is 10.


Radix Sort Step by Step

Let's sort:

[170, 45, 75, 90, 802, 24, 2, 66]

The largest number is 802, which has 3 digits, so we need 3 passes. It helps to imagine every number padded to 3 digits:

170  045  075  090  802  024  002  066

Pass 1: Sort by the ones digit

17[0]  4[5]  7[5]  9[0]  80[2]  2[4]  [2]  6[6]
digits:  0     5     5     0      2     4    2    6

After stable sort by ones digit:
[170, 90, 802, 2, 24, 45, 75, 66]

170 and 90 both end in 0. Since the sort is stable, 170 stays before 90, just as in the input.

Pass 2: Sort by the tens digit

1[7]0  [9]0  8[0]2  [0]2  [2]4  [4]5  [7]5  [6]6
digits:  7     9     0      0     2     4     7     6

After stable sort by tens digit:
[802, 2, 24, 45, 66, 170, 75, 90]

Now the numbers are sorted by their last two digits: 02, 02, 24, 45, 66, 70, 75, 90.

Pass 3: Sort by the hundreds digit

[8]02  [0]02  [0]24  [0]45  [0]66  [1]70  [0]75  [0]90
digits:  8      0      0      0      0      1      0      0

After stable sort by hundreds digit:
[2, 24, 45, 66, 75, 90, 170, 802]

The array is fully sorted.


Radix Sort in Java

import java.util.Arrays;

class Main {

    // Stable counting sort on one decimal digit (exp = 1, 10, 100, ...)
    static void countingSortByDigit(int[] arr, int exp) {

        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];      // digits 0..9

        for (int x : arr) {
            count[(x / exp) % 10]++;
        }

        for (int d = 1; d < 10; d++) {
            count[d] += count[d - 1];
        }

        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            count[digit]--;
            output[count[digit]] = arr[i];
        }

        System.arraycopy(output, 0, arr, 0, n);
    }

    static void radixSort(int[] arr) {

        int max = arr[0];
        for (int x : arr) {
            max = Math.max(max, x);
        }

        // One pass per digit of the largest number
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
            System.out.println("After exp " + exp + ": "
                + Arrays.toString(arr));
        }
    }

    public static void main(String[] args) {

        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

        radixSort(arr);

        System.out.println("Sorted: " + Arrays.toString(arr));
    }
}

Output:

After exp 1: [170, 90, 802, 2, 24, 45, 75, 66]
After exp 10: [802, 2, 24, 45, 66, 170, 75, 90]
After exp 100: [2, 24, 45, 66, 75, 90, 170, 802]
Sorted: [2, 24, 45, 66, 75, 90, 170, 802]

The expression (x / exp) % 10 extracts one digit:

x = 802

exp = 1   → 802 / 1   % 10 = 2   (ones)
exp = 10  → 802 / 10  % 10 = 0   (tens)
exp = 100 → 802 / 100 % 10 = 8   (hundreds)

The loop stops when max / exp becomes 0, meaning the largest number has no more digits.


Why Each Pass Must Be Stable

This is the most important idea in Radix Sort.

Look at 66 and 75. After pass 2, the array was:

[802, 2, 24, 45, 66, 170, 75, 90]
                 ↑         ↑
                66   ...   75     (66 before 75, thanks to passes 1 and 2)

In pass 3, both have hundreds digit 0, so pass 3 sees them as equal. It has no way to know that 66 < 75.

A stable sort keeps them in their current order, 66 before 75, which preserves the work done by the earlier passes. An unstable sort might put 75 before 66, and the final result would be wrong.

LSD Radix Sort only works if the sort used for each digit is stable. Each pass relies on ties being broken by the previous passes.


Radix Sort Complexity

Let:

n = number of elements
d = number of digits in the largest number
b = base (10 for decimal digits)

Each pass is a counting sort with range b, costing O(n + b). There are d passes:

Time  → O(d × (n + b))
Space → O(n + b)

For 32-bit integers in base 10, d is at most 10, a constant. So the time is effectively O(n), linear.

Real implementations often use a bigger base, like 256 (one byte at a time). Then a 32-bit integer needs only 4 passes.

Radix vs Counting Sort

For numbers up to one million (k ≈ 10⁶):

Counting Sort → one pass, but a count array of 1,000,000 ints
Radix Sort    → 7 passes (digits), each with a count array of just 10

Radix Sort trades a few extra passes for a tiny amount of extra memory per pass.


Radix Sort with Negative Numbers

The code above assumes non-negative integers. In Java, -25 % 10 is -5, which would be a negative array index.

Two common fixes:

  • Split: radix-sort the negative numbers by their absolute values, reverse that result and negate it back, then append the sorted non-negative numbers.

  • Offset: subtract the minimum from every element (so all values become ≥ 0), sort, then add the minimum back. Be careful that max - min doesn't overflow int; use long if needed.


A Quick Look at Bucket Sort

A close relative is Bucket Sort. It's often used for values spread evenly over a range, like decimals in [0, 1):

1. Create n empty buckets
2. Put each value x into bucket floor(x × n)
3. Sort each bucket (often with Insertion Sort)
4. Concatenate the buckets

If the values are uniformly distributed, each bucket gets only a few elements, and the average time is O(n). If all values land in one bucket, it degrades to the speed of the sort used inside the bucket.


Common Mistakes

1. Forgetting about negative numbers

count[x] with a negative x throws ArrayIndexOutOfBoundsException. Shift by min.

2. Scanning from the left in the placement step

With the decrement-then-place code, a left-to-right scan reverses equal elements. The output is still sorted for plain numbers, but the sort is unstable, which breaks Radix Sort.

3. Using Counting Sort for a huge range

Always check k. If k is much larger than n, the count array wastes time and memory.

4. Sorting by the most significant digit first with LSD logic

Starting with the hundreds digit and moving to the ones digit (with a plain stable sort each pass) gives a wrong result: the last pass (ones digit) would decide the final order. LSD must go from the least significant digit upward.

5. Integer overflow in exp

If the largest value has 10 digits (at least 1,000,000,000), the step after exp = 1,000,000,000 overflows int. exp becomes a garbage number and the loop runs extra, meaningless passes. Declaring exp as long (and passing it to the digit function as a long) makes the loop stop correctly.


All Sorting Algorithms Compared

Here's a summary of every sorting algorithm covered in this section:

Algorithm

Best

Average

Worst

Extra Space

Stable

Bubble Sort

O(n)*

O(n²)

O(n²)

O(1)

Yes

Selection Sort

O(n²)

O(n²)

O(n²)

O(1)

No

Insertion Sort

O(n)

O(n²)

O(n²)

O(1)

Yes

Merge Sort

O(n log n)

O(n log n)

O(n log n)

O(n)

Yes

Quick Sort

O(n log n)

O(n log n)

O(n²)

O(log n) avg

No

Counting Sort

O(n + k)

O(n + k)

O(n + k)

O(n + k)

Yes**

Radix Sort (LSD)

O(d(n + b))

O(d(n + b))

O(d(n + b))

O(n + b)

Yes

* Bubble Sort is O(n) on sorted input only with the "stop if no swaps" optimisation.
** The prefix-sum version is stable. The simple "write values back from counts" version only works for plain values.

How to choose in practice:

Small or nearly sorted data        → Insertion Sort
Need guaranteed O(n log n) + stable → Merge Sort
Fast general in-memory sort         → Quick Sort (random pivot)
Integers in a small range           → Counting Sort
Many integers with few digits       → Radix Sort
Real code                           → Arrays.sort() / Collections.sort()

Interview Tips and Practice

  • If a problem says values are in a small range (like 0..100, lowercase letters, or 0, 1, 2), think counting first. A frequency array of size 26 for letters is the same idea.

  • Be ready to explain why comparison sorts can't beat O(n log n), and why counting/radix sort don't contradict this (they don't compare).

  • Know why Radix Sort needs a stable sort for each digit.

  • Always mention the catch: Counting Sort costs O(k) extra space, so it only pays off when k is small.

Practice problems:

  • Sort Colors (LeetCode 75): count the 0s, 1s and 2s

  • Relative Sort Array (LeetCode 1122): counting with a fixed range

  • H-Index (LeetCode 274): counting with values capped at n

  • Sort Characters By Frequency (LeetCode 451)

  • Maximum Gap (LeetCode 164): needs linear time, solvable with Radix Sort or buckets

  • Valid Anagram (LeetCode 242): a 26-size count array


The Main Idea

Counting Sort and Radix Sort sort integers without comparing elements, so they can beat the O(n log n) limit of comparison sorts.

Counting Sort:
Count each value
     ↓
Prefix sums give final positions
     ↓
Place elements (right to left for stability)

Radix Sort:
Stable counting sort on ones digit
     ↓
then tens digit
     ↓
then hundreds digit ... until the largest number runs out of digits

Their key facts:

Counting Sort → Time O(n + k),       Space O(n + k),  Stable
Radix Sort    → Time O(d × (n + b)), Space O(n + b),  Stable
Both          → Only for integer-like keys in a limited range

When keys are small integers, stop comparing and start counting: Counting Sort for a small range, Radix Sort for larger numbers with few digits.

This completes our tour of sorting algorithms. In the next chapters, we'll use sorted arrays to power some of the most popular interview techniques, starting with the Two Pointers Technique.