Radix sort

LSD (least significant digit first) processes digits from right to left. Each pass is a stable sort on one digit, and no recursion is needed. It requires keys of the same width, or padding.

MSD (most significant digit first) splits the data into buckets by the first digit and then recursively sorts each bucket by the next digit. It can stop early once a bucket has one element, and it is natural for variable-length strings, but it needs recursion and bookkeeping for many small buckets.

For base 10, create ten buckets numbered 0-9. For each element, in input order, append it to the bucket given by the current digit (x / exp) % 10. Then concatenate the buckets from 0 to 9 back into the array. Repeat with exp = 1, 10, 100, … until max / exp is 0.

Watch the ten digit rows in the animation. After the final pass the array is sorted. The number of passes is the number of digits of the largest value.

1public static void radixSort(int[] arr) {
2    int max = max(arr);
3    for (int exp = 1; max / exp > 0; exp *= 10) {         // least significant digit first
4        List<List<Integer>> bucket = new ArrayList<>();
5        for (int d = 0; d < 10; d++) bucket.add(new ArrayList<>());
6        for (int x : arr) bucket.get((x / exp) % 10).add(x);   // stable distribute
7        int k = 0;
8        for (List<Integer> b : bucket)
9            for (int x : b) arr[k++] = x;                       // gather in digit order
10    }
11}

Each pass must keep elements with the same current digit in their previous relative order. That previous order already reflects all the lower digits, so two numbers tied on the tens digit stay ordered by their ones digit.

If a pass were unstable, the work of the earlier passes would be lost. Appending to buckets in input order, or running counting sort right to left, both give stability. Try “Same last digit” to see 101, 201, 301 survive the first pass in input order.

Fixed-width integers suit LSD directly. Negative integers need care: either offset every value by the minimum, or sort the negative and non-negative values separately and reverse the negatives.

Strings of equal length work with LSD over characters. Strings of different lengths are better handled by MSD, treating a missing character as smaller than any real one, or by padding. Radix sort on strings costs O(total characters), compared with O(n log n) string comparisons that each cost up to the common prefix length.

1// LSD radix sort for equal-length lowercase words
2static void radixSortStrings(String[] words, int length) {
3    for (int pos = length - 1; pos >= 0; pos--) {
4        int[] count = new int[27];
5        for (String w : words) count[w.charAt(pos) - 'a' + 1]++;
6        for (int c = 1; c < count.length; c++) count[c] += count[c - 1];
7        String[] out = new String[words.length];
8        for (String w : words) out[count[w.charAt(pos) - 'a']++] = w;   // left to right with start offsets
9        System.arraycopy(out, 0, words, 0, words.length);
10    }
11}

With base b and d digits, the cost is O(d · (n + b)), where d = ⌈log_b(max + 1)⌉. A larger base means fewer passes but more buckets per pass. A 32-bit integer needs 10 passes in base 10, 4 passes in base 256, and 2 passes in base 65,536.

Base 256 is the usual choice: it extracts one byte per pass with shifts and masks, (x >> (8 * pass)) & 0xFF, and 256 counters fit easily in cache. Very large bases hurt because the bucket array no longer fits in cache.