Lesson 14.4 · Sorting and Divide & Conquer

Counting, Radix and Bucket Sort

When keys are small integers or fixed-width, count them or distribute them instead of comparing: O(n + k) time.

12 min

Think of it like this

Sorting exam papers by grade from 0 to 10: instead of comparing papers, make 11 piles and drop each paper into its grade's pile, then stack the piles in order.

1.Counting sort

If values lie in a small range [0, k), count each value, then write each value as many times as it was counted. O(n + k) time, O(k) space. It's the idea behind int[26] letter counting.

Radix sort applies a stable counting sort digit by digit (least significant first): O(d · (n + base)) for d-digit numbers. Bucket sort spreads values over buckets by range and sorts each small bucket.

CountingSort.java

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] grades = {7, 3, 9, 3, 10, 0, 7, 7};
        int[] count = new int[11];
        for (int g : grades) count[g]++;
        int k = 0;
        for (int v = 0; v <= 10; v++)
            while (count[v]-- > 0) grades[k++] = v;
        System.out.println(Arrays.toString(grades));
    }
}

Output

[0, 3, 3, 7, 7, 7, 9, 10]

Remember

Counting sort: O(n + k) for values in [0, k).
Radix sort: digit by digit with a stable counting sort.
Only for integer-like keys with a bounded range.

Common mistakes

Using counting sort with a huge range (memory explodes).
Using an unstable sort per digit in radix sort.

Command Palette

Counting, Radix and Bucket Sort

1.Counting sort