Radix Sort processes integers one digit at a time, from least significant digit (LSD) to most significant digit (MSD), applying a stable sort (typically Counting Sort) at each digit position. The result is a fully sorted array in O(d·(n+k)) time, where d is the number of digits and k is the base.
void countSortByDigit(vector<int>& arr, int exp) {
int n = arr.size();
vector<int> output(n); int count[10] = {};
for (int i = 0; i < n; i++) count[(arr[i]/exp)%10]++;
for (int i = 1; i < 10; i++) count[i] += count[i-1];
for (int i = n-1; i >= 0; i--) output[--count[(arr[i]/exp)%10]] = arr[i];
arr = output;
}
void radixSort(vector<int>& arr) {
int maxVal = *max_element(arr.begin(), arr.end());
for (int exp = 1; maxVal/exp > 0; exp *= 10) countSortByDigit(arr, exp);
}Radix Sort sorts integers one digit at a time. Starting from the least significant digit ensures stability: later passes on more significant digits do not disturb the relative order set by earlier passes.
Each digit pass uses Counting Sort on base-10 digits (values 0-9). Because Counting Sort is stable and k=10 is constant, each pass is O(n). Total time is O(d*n) where d is the number of digits.
LSD Radix Sort (least significant digit first) is easier to implement iteratively and works well for fixed-length integers. MSD (most significant digit first) is better for variable-length strings and allows early termination.
Radix Sort excels when sorting large arrays of integers with a small digit count — e.g., 32-bit integers have d=10 decimal digits. It beats comparison sorts for large n but uses O(n) extra space.
Quiz coming soon for this algorithm.