Radix Sort is a non-comparison integer sorting algorithm that processes numbers digit by digit from the least significant to the most significant. It distributes each number into different “buckets” based on the value of the current digit, then collects the numbers back into the original array in the order of the buckets. This process is repeated until all digits are processed. This method is particularly suitable for integers with fewer digits and has high efficiency.

Basic Idea of Radix Sort¶

1. Distribution: Distribute numbers into corresponding buckets based on the current digit (e.g., units place, tens place, hundreds place). For example, numbers with a units digit of 3 are placed into bucket 3, and numbers with a tens digit of 2 are placed into bucket 2.
2. Collection: Take out the numbers from the buckets in order (from 0 to 9) and put them back into the original array, completing one digit’s sorting.
3. Repetition: Repeat the above distribution and collection process for each digit (from the least significant to the most significant) until all digits are processed.

Example of Sorting Process¶

Take the array [5, 3, 8, 12, 23, 100] as an example to demonstrate the sorting process step by step:

Initial Array¶

[5, 3, 8, 12, 23, 100]

First Round: Process the Units Digit (radix=1)¶

The units digits of each number are: 5 (units digit 5), 3 (units digit 3), 8 (units digit 8), 12 (units digit 2), 23 (units digit 3), 100 (units digit 0).
- Distribution into buckets:
Bucket 0: [100], Bucket 2: [12], Bucket 3: [3, 23], Bucket 5: [5], Bucket 8: [8]; other buckets are empty.
- Collection back to array: [100, 12, 3, 23, 5, 8].

Second Round: Process the Tens Digit (radix=10)¶

The tens digits of each number are: 100 (tens digit 0), 12 (tens digit 1), 3 (tens digit 0), 23 (tens digit 2), 5 (tens digit 0), 8 (tens digit 0).
- Distribution into buckets:
Bucket 0: [100, 3, 5, 8], Bucket 1: [12], Bucket 2: [23]; other buckets are empty.
- Collection back to array: [100, 3, 5, 8, 12, 23].

Third Round: Process the Hundreds Digit (radix=100)¶

The hundreds digits of each number are: 100 (hundreds digit 1), 3 (hundreds digit 0), 5 (hundreds digit 0), 8 (hundreds digit 0), 12 (hundreds digit 0), 23 (hundreds digit 0).
- Distribution into buckets:
Bucket 0: [3, 5, 8, 12, 23], Bucket 1: [100]; other buckets are empty.
- Collection back to array: [3, 5, 8, 12, 23, 100].

Sorting is complete!

Java Code Implementation¶

import java.util.ArrayList;
import java.util.List;

public class RadixSort {

    public static void radixSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return; // Return directly for empty array
        }

        // 1. Find the maximum number to determine the highest digit
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }

        // 2. Process digits from least significant to most significant (units, tens, hundreds...)
        for (int radix = 1; max / radix > 0; radix *= 10) {
            // Create 10 buckets (0-9) using ArrayList for dynamic storage
            List<List<Integer>> buckets = new ArrayList<>();
            for (int i = 0; i < 10; i++) {
                buckets.add(new ArrayList<>());
            }

            // 3. Distribute: Place each number into the corresponding bucket based on current digit
            for (int num : arr) {
                int currentDigit = (num / radix) % 10; // Get current digit
                buckets.get(currentDigit).add(num);
            }

            // 4. Collect: Return numbers from buckets to the original array in order
            int index = 0;
            for (List<Integer> bucket : buckets) {
                for (int num : bucket) {
                    arr[index++] = num;
                }
            }
        }
    }

    // Test code
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 12, 23, 100};
        System.out.println("Before sorting: " + java.util.Arrays.toString(arr));
        radixSort(arr);
        System.out.println("After sorting: " + java.util.Arrays.toString(arr));
    }
}

Key Points of Code Explanation¶

1. Find Maximum Number: Determine the highest digit to process (e.g., for max=100, process the hundreds place).
2. Get Current Digit: Calculate the current digit using (num / radix) % 10. For example:
   - Units place: radix=1 → (num / 1) % 10 directly gets the units digit.
   - Tens place: radix=10 → (num / 10) % 10 gets the tens digit.
3. Bucket Distribution and Collection: Use ArrayList to dynamically store elements in buckets, avoiding pre-determined capacity. Numbers are collected back into the original array in order.

Time and Space Complexity¶

• Time Complexity: O(d*(n+k)), where d is the number of digits in the maximum number, n is the array length, and k is the radix (here k=10). If d and k are fixed, the time complexity approximates O(n).
• Space Complexity: O(n+k), requiring n space for the array and k space for the buckets.

Summary¶

Radix Sort achieves sorting through the “distribute-collect by digit” approach, suitable for integer sorting, especially efficient when numbers have fewer digits. The code uses ArrayList as buckets to simplify dynamic storage and maintains sorting stability (relative order of equal numbers remains unchanged). For negative numbers, separate positive and negative numbers, sort them separately, then merge the results.