Radix Sort Implementation

Problem Statement

Sort an array of non-negative integers using LSD radix sort: sort by the least significant digit first, then each more significant digit, using a stable sort at each step.

Example

Input:  [170, 45, 75, 90, 2, 802, 24, 66]
By ones -> by tens -> by hundreds
Output: [2, 24, 45, 66, 75, 90, 170, 802]

Approach

Process digits from least to most significant. At each digit, run a stable counting sort using that digit as the key. Because each pass preserves the order established by earlier (less significant) passes, the array ends up fully sorted after the most significant digit.

Complexity

• Time: O(d(n + k)), d = number of digits, k = base (10)
• Space: O(n + k)

Solution Code

Python

def radix_sort(arr):
    if not arr:
        return arr
    max_v = max(arr)
    exp = 1
    while max_v // exp > 0:
        arr = _count_by_digit(arr, exp)
        exp *= 10
    return arr

def _count_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for x in arr:
        count[(x // exp) % 10] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    for i in range(n - 1, -1, -1):
        d = (arr[i] // exp) % 10
        output[count[d] - 1] = arr[i]
        count[d] -= 1
    return output

Java

int[] radixSort(int[] arr) {
    if (arr.length == 0) return arr;
    int maxV = arr[0];
    for (int x : arr) maxV = Math.max(maxV, x);
    for (int exp = 1; maxV / exp > 0; exp *= 10) {
        int[] output = new int[arr.length];
        int[] count = new int[10];
        for (int x : arr) count[(x / exp) % 10]++;
        for (int i = 1; i < 10; i++) count[i] += count[i - 1];
        for (int i = arr.length - 1; i >= 0; i--) {
            int d = (arr[i] / exp) % 10;
            output[--count[d]] = arr[i];
        }
        arr = output;
    }
    return arr;
}

C++

vector<int> radixSort(vector<int> arr) {
    if (arr.empty()) return arr;
    int maxV = *max_element(arr.begin(), arr.end());
    for (int exp = 1; maxV / exp > 0; exp *= 10) {
        vector<int> output(arr.size());
        int count[10] = {0};
        for (int x : arr) count[(x / exp) % 10]++;
        for (int i = 1; i < 10; i++) count[i] += count[i - 1];
        for (int i = (int)arr.size() - 1; i >= 0; i--) {
            int d = (arr[i] / exp) % 10;
            output[--count[d]] = arr[i];
        }
        arr = output;
    }
    return arr;
}

Key Takeaways

• Radix sort needs a stable per-digit sort to work correctly.
• Great for fixed-width integers/strings; the shown version assumes non-negative integers.
• Reference: CLRS, Ch. 8; Wikipedia, "Radix sort".