Radix sort

›Short versionOpen if you only have a minute.

Least-significant-digit radix sort orders the array by the ones place, then the tens, then each higher place.
The sort is stable because each digit pass is a stable counting sort. An unstable digit pass would undo the order built by earlier digits.
Each pass allocates an output array of length n and a count array of length 10. Extra memory is O(n + base).
Time is O(d(n + base)), where d is the number of digits in the largest key. A few enormous keys make d the expensive part.
The routine below accepts non-negative ints. Arrays.sort on an int array is the JDK dual-pivot quicksort. Object arrays go to Timsort.

One stable pass per digit

The outer loop’s exp is 1, then 10, then 100, and so on, while max / exp is still positive. For a given place, the digit is (value / exp) % 10. A counting sort on that digit, using a table of length 10, rewrites the array. The next place sees an array that is already ordered by every place beneath it.

On [170, 45, 75, 90] the ones pass yields [170, 90, 45, 75], with the two trailing zeros and the two trailing fives still in their original order. The tens pass yields [45, 170, 75, 90]. The hundreds pass yields [45, 75, 90, 170].

Stable only for the whole width

Radix sort is a . The keys in this implementation are non-negative ints. Equal ints are identical, so the printed numbers hide the order of ties. The same passes, applied to records and keyed by an integer field, keep equal keys in their original order. The code here is the least-significant-digit form.

Each pass allocates fresh arrays, so the sort uses . Time is one counting sort per digit: O(d(n + 10)) with this base. The worst case is a large d, a key with many digits, even when n is modest. exp is a long so the step from 1_000_000_000 to the next power of ten does not overflow an int and keep the loop alive.

After the ones pass, the array is [21, 22]. The tens digits are equal. What does an unstable tens pass risk?

It can emit [22, 21]. Both tens digits are 2, so an unstable pass is free to swap them. That swap throws away the ones-digit order, where 1 belongs before 2. A stable pass leaves [21, 22] alone.

When the library sort takes over

For an ordinary int[], Arrays.sort is a . Object arrays, and any order defined by a comparator, belong to . Negative keys need a separate treatment: Java’s remainder can be negative, and a negative digit cannot index the count table. The method below rejects them.

RadixSort.java

public class RadixSort {
    static void radixSort(int[] arr) {
        if (arr.length == 0) {
            return;
        }
        int max = 0;
        for (int value : arr) {
            if (value < 0) {
                throw new IllegalArgumentException("radix sort expects non-negative keys");
            }
            if (value > max) {
                max = value;
            }
        }
        for (long exp = 1; max / exp > 0; exp *= 10) {
            countByDigit(arr, exp);
        }
    }

    static void countByDigit(int[] arr, long exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];
        for (int value : arr) {
            count[(int) ((value / exp) % 10)]++;
        }
        for (int digit = 1; digit < 10; digit++) {
            count[digit] += count[digit - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            int digit = (int) ((arr[i] / exp) % 10);
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }
        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr);
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}