Radix Sort Algorithm

What is Radix Sort?

Radix Sort is a non-comparison-based sorting algorithm that sorts numbers by processing their individual digits. It works by sorting the input numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD).

Unlike traditional comparison sorts (like Quick Sort or Merge Sort), Radix Sort does not compare elements directly. Instead, it groups numbers by each digit using a stable sorting algorithm (commonly Counting Sort) as a subroutine.

How Radix Sort Works

1. Find the maximum number to determine the number of digits.
2. Start with the least significant digit (rightmost).
3. Use a stable sort (e.g., Counting Sort) to sort elements based on the current digit.
4. Repeat the process for each digit position, moving left.

For example, to sort numbers by the hundreds place, we ensure the list is already stably sorted by the tens and units digits.

Characteristics of Radix Sort

• Efficient for sorting large numbers with a known number of digits.
• Stable: maintains the relative order of equal elements.
• Works best when numbers are uniformly distributed and have similar length.

When to Use

Use Radix Sort when:

• You need to sort integers or fixed-length strings.
• You require linear time sorting and the maximum value is not very large.
• Stability of sort is important (e.g., sorting IDs or dates).

Time & Space Complexity

Where:

• n = number of elements
• k = number of digits in the largest number
  (For base-10, k ≈ log₁₀(max element))

Code Example

public class RadixSortExample {

    // Main radix sort method
    public static void radixSort(int[] arr) {
        int max = getMax(arr);

        // Apply counting sort for each digit (LSD to MSD)
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    // Helper method to get the maximum value
    public static int getMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) max = num;
        }
        return max;
    }

    // Counting Sort based on the current digit (exp)
    public static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10]; // For digits 0–9

        // Count digit occurrences
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % 10;
            count[digit]++;
        }

        // Convert count to position indices
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Build the output array (stable sort)
        for (int i = n - 1; i >= 0; i--) {
            int digit = (arr[i] / exp) % 10;
            output[count[digit] - 1] = arr[i];
            count[digit]--;
        }

        // Copy sorted output back into original array
        System.arraycopy(output, 0, arr, 0, n);
    }

    public static void printArray(int[] arr) {
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        System.out.println("Original array:");
        printArray(arr);

        radixSort(arr);

        System.out.println("Sorted array:");
        printArray(arr);
    }
}

Output

Original array:
170 45 75 90 802 24 2 66 
Sorted array:
2 24 45 66 75 90 170 802 

Radix Sort – Visual Explanation (Step-by-Step)

Let’s sort this array:

[170, 45, 75, 90, 802, 24, 2, 66]

Step 1: Sort by unit’s place (exp = 1)

Sort by last digit:

[170, 90, 802, 2, 24, 45, 75, 66]
 → Sorted: [170, 90, 802, 2, 24, 45, 75, 66]

Last digits: 0, 5, 5, 0, 2, 4, 2, 6
→ After stable sort:

[170, 90, 802, 2, 24, 45, 75, 66]

Step 2: Sort by ten’s place (exp = 10)

Digits: 7, 4, 7, 9, 0, 2, 6, 6
→ After stable sort:

[802, 2, 24, 45, 66, 75, 170, 90]

Step 3: Sort by hundred’s place (exp = 100)

Digits: 8, 0, 0, 0, 0, 0, 1, 0
→ After stable sort:

[2, 24, 45, 66, 75, 90, 170, 802]

Final Sorted Array

[2, 24, 45, 66, 75, 90, 170, 802]

Summary

• Radix Sort is one of the fastest sorting algorithms for integers and strings with a known length or digit count.
• It does not use comparisons and relies on digit-based sorting.
• It is stable, has linear time complexity, and is particularly effective for large datasets with bounded values.