Idea: Count frequency of elements

• Time: O(n + k)
• Space: O(k)
• Stable: ✅

Limit

• Only for small integer ranges

public class CountingSort {
    public static void sortNonNegative(int[] a) {
        if (a.length == 0) return;

        int max = a[0];
        for (int v : a) {
            if (v < 0) throw new IllegalArgumentException("Only non-negative integers supported.");
            if (v > max) max = v;
        }

        int[] count = new int[max + 1];
        for (int v : a) count[v]++;

        // prefix sums for stable output
        for (int i = 1; i < count.length; i++) count[i] += count[i - 1];

        int[] out = new int[a.length];
        for (int i = a.length - 1; i >= 0; i--) { // reverse keeps stability
            int v = a[i];
            out[--count[v]] = v;
        }

        System.arraycopy(out, 0, a, 0, a.length);
    }
}

Watch for

• Counting frequencies
• Rebuilding array from counts

Mental model: 📊 Count → rebuild