Idea: Sort digit by digit

• Time: O(n × d)
• Stable: ✅

Used for

• Large integers
• Strings (fixed length)

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

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

        // sort by each digit (1s, 10s, 100s, ...)
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingByDigit(a, exp);
        }
    }

    private static void countingByDigit(int[] a, int exp) {
        int n = a.length;
        int[] out = new int[n];
        int[] count = new int[10];

        for (int v : a) count[(v / exp) % 10]++;

        for (int i = 1; i < 10; i++) count[i] += count[i - 1];

        for (int i = n - 1; i >= 0; i--) { // stable
            int v = a[i];
            int d = (v / exp) % 10;
            out[--count[d]] = v;
        }

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

Watch for

• Digit-by-digit sorting
• Stability matters

Mental model: 🔢 Sort by digits, not values