Radix Sort Algorithm in DSA C++

Mental Model

Radix sort sorts numbers by processing digits from least to most significant, grouping numbers by each digit step.

Analogy: Imagine sorting mail by zip code: first by the last digit, then the second last, and so on, until fully sorted.

Array: [170, 45, 75, 90, 802, 24, 2, 66]
Buckets for digits 0-9:
0: []
1: []
2: []
3: []
4: []
5: []
6: []
7: []
8: []
9: []

Dry Run Walkthrough

Input: list: [170, 45, 75, 90, 802, 24, 2, 66]

Goal: Sort the list using radix sort by processing digits from least significant to most significant

Step 1: Sort by least significant digit (ones place)

Buckets:
0: [170, 90]
2: [802, 2]
4: [24]
5: [45, 75]
6: [66]
Others: []
Reassembled array: [170, 90, 802, 2, 24, 45, 75, 66]

Why: Group numbers by their ones digit to partially sort by that digit

Step 2: Sort by second least significant digit (tens place)

Buckets:
0: [802, 2]
2: [24]
4: [45]
6: [66]
7: [170, 75]
9: [90]
Others: []
Reassembled array: [802, 2, 24, 45, 66, 170, 75, 90]

Why: Group numbers by their tens digit to refine sorting

Step 3: Sort by third least significant digit (hundreds place)

Buckets:
0: [2, 24, 45, 66, 75, 90]
1: [170]
8: [802]
Others: []
Reassembled array: [2, 24, 45, 66, 75, 90, 170, 802]

Why: Group numbers by their hundreds digit to finalize sorting

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to get digit at given place
int getDigit(int num, int place) {
    return (num / place) % 10;
}

// Radix sort function
void radixSort(vector<int>& arr) {
    if (arr.empty()) return;
    int maxVal = *max_element(arr.begin(), arr.end());
    // Start with least significant digit place = 1
    for (int place = 1; maxVal / place > 0; place *= 10) {
        vector<vector<int>> buckets(10);
        // Place elements into buckets based on current digit
        for (int num : arr) {
            int digit = getDigit(num, place);
            buckets[digit].push_back(num);
        }
        // Reassemble array from buckets
        int index = 0;
        for (const auto& bucket : buckets) {
            for (int num : bucket) {
                arr[index++] = num;
            }
        }
    }
}

int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

for (int place = 1; maxVal / place > 0; place *= 10) {

iterate over digit places from least significant to most significant

for (int num : arr) { int digit = getDigit(num, place); buckets[digit].push_back(num); }

group numbers into buckets by current digit

for (const auto& bucket : buckets) { for (int num : bucket) { arr[index++] = num; } }

reassemble array from buckets preserving order

Output

2 24 45 66 75 90 170 802 

Complexity Analysis

Time: O(d * (n + k)) where d is number of digits, n is number of elements, k is bucket count (10); because we process each digit and distribute elements into buckets

Space: O(n + k) for buckets to hold elements temporarily during sorting

vs Alternative: Compared to comparison sorts like quicksort O(n log n), radix sort can be faster for fixed digit sizes but uses extra space for buckets

Edge Cases

Empty array

Function returns immediately without error and array remains empty

DSA C++

if (arr.empty()) return;

Array with one element

Array remains unchanged after sorting

DSA C++

for (int place = 1; maxVal / place > 0; place *= 10) {

Array with duplicate numbers

Duplicates are preserved and sorted correctly

DSA C++

buckets[digit].push_back(num);

When to Use This Pattern

When you need to sort integers or fixed-length strings efficiently without comparisons, reach for radix sort because it sorts by digits in linear time.

Common Mistakes

Mistake: Not processing all digit places up to the maximum number's length
Fix: Use a loop that continues while maxVal / place > 0 to cover all digits

Mistake: Reassembling array incorrectly by mixing bucket order
Fix: Reassemble by iterating buckets in order from 0 to 9 to maintain digit order

Summary

Radix sort sorts numbers digit by digit from least to most significant.

Use it when sorting integers or fixed-length data where comparison-based sorts are slower.

The key insight is grouping numbers by each digit to gradually build a fully sorted list.