Java Radix Sort for Fast Integer and String Sorting

Introduction

Radix sort java programmers use it when they need to sort integers or strings in linear time without comparing keys. The algorithm was invented by Herman Hollerith for the 1890 United States census, where punch cards were sorted by column using a mechanical tabulating machine. The modern computer version was formalised by Harold Seward in 1954 in his MIT master's thesis, which introduced both counting sort and radix sort. The algorithm was later refined by Donald Knuth in The Art of Computer Programming Volume 3 (1973), who distinguished the least significant digit (LSD) variant from the most significant digit (MSD) variant and analysed their running times as O(d times (n plus k)) where d is the digit count.

For a Java learner, radix sort java demonstrates how a clever combination of stable sub sorts can beat the O(n log n) comparison lower bound. By sorting digits one at a time, from least significant to most significant, and using a stable sub sort at each step, the algorithm produces a fully sorted array in O(d times n) time where d is the number of digit positions. Building radix sort from scratch teaches the link between stability and composition of sorts, which appears again in bucket sort and in database query planners that sort by multiple columns.

What is Radix Sort?

Radix sort is a non comparison, distribution sort that processes keys digit by digit, using a stable sub sort at each digit position. It belongs to the distribution sort family alongside counting sort and bucket sort. Unlike comparison sorts, radix sort never compares two keys directly, so it sidesteps the O(n log n) lower bound on comparison sorts. The catch is that keys must be expressible as a sequence of digits drawn from a fixed alphabet, which works naturally for integers and fixed length strings.

Two variants exist. LSD radix sort starts from the least significant digit and moves towards the most significant. Each pass must be a stable sort, so that ties on a given digit preserve the order produced by previous passes on less significant digits. MSD radix sort starts from the most significant digit and partitions the input into buckets by the first digit, then recursively sorts each bucket on the next digit. MSD radix sort does not require stability between passes, but it does require recursion or an explicit stack.

For integer keys, each digit is usually base 10, base 16, or base 256. A larger base means fewer passes but a larger count array per pass. The base is a tunable parameter that trades memory for passes.

How Radix Sort Works - Step by Step

Step 1: Choose a base. For base 10 integers, each digit is a single decimal digit from 0 to 9, and the count array has 10 slots. For base 256, each digit is a byte from 0 to 255, and the count array has 256 slots. We use base 10 in this example for clarity.

Step 2: Find the maximum key. The number of passes is the number of digits in the maximum key. If the maximum key is 802, we need 3 passes for the units, tens, and hundreds digits.

Step 3: For each digit position, run a stable counting sort keyed on that digit. For the units pass, extract the units digit of each key by computing key modulo 10. For the tens pass, extract the tens digit by computing key divided by 10 modulo 10. For the hundreds pass, extract the hundreds digit by computing key divided by 100 modulo 10.

Step 4: Stability preserves ordering. After the units pass, the array is sorted by the units digit only, but the original order is preserved among items with the same units digit. After the tens pass, the array is sorted by tens then units, because the stable tens pass preserves the units ordering within each tens group. After the hundreds pass, the array is fully sorted by hundreds then tens then units.

Step 5: Stop when all digits of the maximum key have been processed. Any further passes would extract a digit of 0 from every key, so the array is unchanged.

Java Program for Radix Sort

public class RadixSortDemo {

    // Sorts an array of non negative integers using LSD radix sort
    // with base 10. The input array is sorted in place.
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }

        // Step 1: find the maximum key to know the digit count.
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        // Step 2: do one counting sort pass per digit position.
        // exp is 1, then 10, then 100, then 1000, and so on.
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    // Stable counting sort on the digit at position exp.
    // digit = (key / exp) % 10
    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10];

        // Count frequencies of each digit 0 to 9.
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }

        // Convert frequencies to prefix sums.
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Walk backwards to preserve stability.
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            count[digit]--;
            output[count[digit]] = arr[i];
        }

        // Copy the stable output back into the input array.
        for (int i = 0; i < n; i++) {
            arr[i] = output[i];
        }
    }

    public static void main(String[] args) {
        int[] data = {170, 45, 75, 90, 802, 24, 2, 66};

        System.out.print("Input:  ");
        for (int v : data) {
            System.out.print(v + " ");
        }
        System.out.println();

        radixSort(data);

        System.out.print("Output: ");
        for (int v : data) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

Code Explanation - Line by Line

The radixSort method starts by finding the maximum key in the array. The maximum key tells us how many digit positions we need to process. If the maximum is 802, the hundreds digit is the last non zero position, so we need exactly three passes.

The outer loop walks exp through powers of 10. exp starts at 1 (units), then becomes 10 (tens), then 100 (hundreds), and so on. The loop condition max divided by exp greater than 0 ensures we stop after processing the most significant digit of the maximum key. For max equals 802, exp takes the values 1, 10, and 100, then stops because 802 divided by 1000 equals 0.

The countingSortByDigit method is a stable counting sort keyed on the digit at position exp. The digit is extracted by integer division by exp, then modulo 10. For exp equals 1, this gives the units digit. For exp equals 10, this gives the tens digit. For exp equals 100, this gives the hundreds digit.

The count array has 10 slots because each decimal digit ranges from 0 to 9. We count frequencies, convert to prefix sums, walk the input backwards to preserve stability, and copy the output back to the input array. This is exactly the counting sort from the previous post, specialised to a 10 element range.

The backwards walk in the placement loop is essential. Without it, items with the same digit at the current position would appear in the output in reverse order from their input order, breaking the stability that the algorithm relies on to compose digit sorts into a full sort.

Sample Input and Output

Input:  170 45 75 90 802 24 2 66
Output: 2 24 45 66 75 90 170 802

The output is sorted ascending. After the units pass, the array is sorted by units digit only. After the tens pass, the array is sorted by tens then units. After the hundreds pass, the array is fully sorted. Three passes of counting sort on 10 element ranges produce the final sorted array, which is why the total running time is O(d times (n plus k)) where d is the number of digits and k is 10.

Common Mistakes to Avoid

First, do not use an unstable sub sort between passes. If the sub sort at each digit position is not stable, the composition of digit sorts will not produce a fully sorted array. Always use a stable sub sort, typically counting sort, and always walk the input backwards during placement.

Second, do not forget to handle the most significant digit correctly. If the loop stops one pass too early, the most significant digit is never processed and the array is sorted only on the lower digits. Use the loop condition max divided by exp greater than 0 to stop exactly when no further non zero digit exists.

Third, do not assume the input is non negative. For negative integers, you must either shift the keys to be non negative before sorting, or use a signed variant that processes the sign bit separately. A common trick is to flip the sign bit, sort as unsigned, then flip back.

Fourth, do not use base 10 blindly. For 32 bit integers, base 10 needs 10 passes, but base 256 needs only 4 passes and base 65536 needs only 2 passes. The optimal base balances the count array size against the number of passes. In practice, base 256 is a good default.

Real-World Applications

Radix sort powers many high performance sorting libraries. The GNU C library, the Linux kernel, and the bsd qsort all use radix sort variants for sorting fixed width integers when the key count is large. The java.util.Arrays.parallelSort method uses a merge sort, not radix sort, because it must handle arbitrary object types.

Suffix array construction for string indexing uses MSD radix sort as a sub routine in the deep-shallow algorithm of Manzini and Ferragina (2004), which builds the suffix array in linear time for practical inputs. The algorithm runs radix sort on the first few characters, then switches to a different algorithm for the deep suffixes.

In database engines, radix sort is used to sort fixed width integer columns when the row count is large enough that the linear pass count beats the comparison overhead. Many columnar databases such as ClickHouse and Apache Arrow use radix sort as the default for integer columns, because it is cache friendly and parallelises well across threads.

In competitive programming, radix sort is used when n is huge and the keys are 32 bit integers, because it avoids the O(n log n) comparison cost and runs in O(n) time for fixed width keys.

Conclusion

We built LSD radix sort from scratch and saw how stable counting sort applied digit by digit produces a fully sorted array in O(d times n) time. We learned that stability is the composition glue that lets us sort by tens then units and end up with a tens plus units ordering. Next, study bucket sort, which generalises the same idea to floating point keys, and MSD radix sort, which uses recursion instead of stability to sort variable length strings.