Sorting / Non-Comparison Radix Sort Medium

Radix Sort — Sort Digit by Digit

Process digits from least significant to most significant, using counting sort as a stable subroutine. O(D × (N + 10)) time.

Radix Sort — Non-Comparison Sort
Not completed
GFG
Practice this algorithm on GeeksforGeeks to reinforce your understanding.
Open Problem

What does it solve?

Sorts non-negative integers by processing individual digits. Starting from the least significant digit (ones), it uses a stable sort (counting sort) on each digit position, moving up to tens, hundreds, etc.

Key insight: because each pass uses a stable sort, the relative order from previous passes is preserved. After processing all D digits, the array is fully sorted. No element comparisons needed.

The Process

// Extract digit at position exp
digit = (val / exp) % 10

// For each digit position (1, 10, 100...):
1. Distribute into buckets 0..9
2. Collect from buckets in order
3. Move to next digit position
Interactive Visualization
Current Element
Active Digit
Distributing
Collected / Done
Current Array
Digit Buckets (0-9)
Press Play or Next to begin
Result after pass
—
Step 0 of 0
Phase
Init
Digit Place
—
Pass
0
Total Passes
0
Ready. Press Play or Next to start the Radix Sort animation.
✓ Sorted
Speed
Step-by-Step Walkthrough
Phase Description
1. Find MaxDetermine maximum value to know how many digit passes are needed (D = number of digits in max).
2. DistributeFor current digit place (ones, tens...), extract each element's digit and place into bucket 0-9.
3. CollectRead buckets 0 through 9 in order, concatenating back into the array. Stability is preserved.
4. RepeatMove to next digit place (× 10). Repeat until all digit places are processed.
C++ — Radix Sort (LSD) 
void countingSortByDigit(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<int> output(n), count(10, 0);

    // Count occurrences of each digit
    for (int val : arr)
        count[(val / exp) % 10]++;

    // Prefix sum
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Place elements (right to left for stability)
    for (int i = n - 1; i >= 0; i--) {
        int d = (arr[i] / exp) % 10;
        output[count[d] - 1] = arr[i];
        count[d]--;
    }
    arr = output;
}

void radixSort(vector<int>& arr) {
    int mx = *max_element(arr.begin(), arr.end());

    // Process each digit place
    for (int exp = 1; mx / exp > 0; exp *= 10)
        countingSortByDigit(arr, exp);
}
Complexity
Time
O(D × (N+K))

D = number of digits in max, N = elements, K = base (10). Linear when D is constant.

Space
O(N + K)

Output array of size N plus count array of size K (10 for decimal).

Stable?
Yes

Uses stable counting sort as subroutine. Essential for correctness.

In-Place?
No

Requires output and count arrays each pass.

📝 Notes

▼