How to Implement the Radix Sort Algorithm

Introduction

Sorting is a fundamental operation in computer science. While many are familiar with algorithms based on comparisons like for instance quicksort and Merge Sort, Radix Sort stands out for being non-comparative and very efficient for specific scenarios, mainly when dealing with integers. In this article, we’ll explain what Radix Sort is, how it works, how it can be implemented in Java, and its complexity.

Basics Information on Radix Sort

Radix Sort is a sorting algorithm not based on comparisons that sorts numbers a digit at a time, starting from the least significant digit to the most significant digit. It uses a stable algorithm like Counting Sort to group elements at each digit level. Radix Sort works best when sorting integers or fixed-length strings and there is the need for linear-time sorting.

How Does Radix Sort Work?

Let’s say you have the numbers:
[170, 45, 75, 90, 802, 24, 2, 66]

Radix Sort will:

1. Sort based on the 1s digit → [170, 90, 802, 2, 24, 45, 75, 66]
2. Then the 10s digit → [802, 2, 24, 45, 66, 170, 75, 90]
3. Then the 100s digit → [2, 24, 45, 66, 75, 90, 170, 802]

After sorting all digit places, the list is sorted!

Java Implementation of Radix Sort

Here’s a simple and clean implementation of Radix Sort in Java:

	@Test
	public void RadixSortTest() throws Exception {
        int[] arrToBeSorted = {55, 66, 88, 99, 677, 55, 25, 77};
        radixSortingArr(arrToBeSorted);
		for (int elem : arrToBeSorted) {
			System.out.println(elem + " ");
		}
	}

    private int getMaxVal(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
        }
        return max;
    }

    private void cSort(int[] arrToBeSorted, int exp) {
        int N = arrToBeSorted.length;
        int[] out = new int[N];
        int[] count = new int[10];
        
        for (int num : arrToBeSorted) {
            int dig = (num / exp) % 10;
            count[dig]++;
        }
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        for (int i = N - 1; i >= 0; i--) {
            int digit = (arrToBeSorted[i] / exp) % 10;
            out[count[digit] - 1] = arrToBeSorted[i];
            count[digit]--;
        }
        System.arraycopy(out, 0, arrToBeSorted, 0, N);
    }

    private void radixSortingArr(int[] arr) {
        int max = getMaxVal(arr);
        for (int exp = 1; max / exp > 0; exp *= 10) {
        	cSort(arr, exp);
        }
    }

Time and Space Complexity

O(n * k) — where n is the number of elements and k is the number of digits in the largest number

O(n + k) — extra space for count and output arrays

Note: Radix Sort doesn’t work well for floating-point numbers or negative integers.

When to Use Radix Sort

Radix Sort is a good choice when the following is true:

• Large lists of integers
• Not too wide a range of numbers
• Need to avoid comparison sorting

Final Thoughts

Radix Sort is a brilliant example of how knowing the structure of your data can lead to powerful optimizations. Though it’s not as general-purpose as Quick Sort, it can outperform traditional methods under the right conditions.

You can find the example code on Github.