Radix Sort
I. In-Class Exercises
Programming Exercises
- Radix Sort: L50002
II. Knowledge Summary
Core Idea
Radix Sort is a non-comparison sorting algorithm that achieves overall sorting through digit-by-digit sorting. It splits integers by digit and performs a stable sort (usually counting sort) on each digit position, repeating multiple times until the entire array is sorted.
There are two approaches to radix sort:
- LSD (Least Significant Digit): Starts from the least significant digit (ones place) and works toward higher digits. Most commonly used.
- MSD (Most Significant Digit): Starts from the most significant digit and works toward lower digits. Suitable for string sorting.
LSD Radix Sort Principle
LSD starts from the ones place, and each round performs a stable counting sort on the current digit. After d rounds (where d is the maximum number of digits), the array is fully sorted.
Why must it be a stable sort? Because the results of lower-digit sorting must be preserved during higher-digit sorting. If the higher digits are the same, the order from lower digits must be maintained.
1#include <bits/stdc++.h>
2using namespace std;
3
4// Get the digit of number x at position exp (exp = 1, 10, 100, ...)
5int getDigit(int x, int exp) {
6 return (x / exp) % 10;
7}
8
9// Perform counting sort on the array by the digit at position exp (stable sort)
10void countingSortByDigit(int a[], int n, int exp) {
11 int output[100005];
12 int count[10] = {0};
13
14 // Count occurrences of each digit
15 for (int i = 0; i < n; i++)
16 count[getDigit(a[i], exp)]++;
17
18 // Compute prefix sums to determine final positions
19 for (int i = 1; i < 10; i++)
20 count[i] += count[i - 1];
21
22 // Traverse from back to front to ensure stability
23 for (int i = n - 1; i >= 0; i--) {
24 int d = getDigit(a[i], exp);
25 output[count[d] - 1] = a[i];
26 count[d]--;
27 }
28
29 // Copy back to the original array
30 for (int i = 0; i < n; i++)
31 a[i] = output[i];
32}
33
34void radixSort(int a[], int n) {
35 // Find the maximum value to determine the number of digits
36 int maxVal = *max_element(a, a + n);
37
38 // Sort digit by digit from ones to the highest digit
39 for (int exp = 1; maxVal / exp > 0; exp *= 10) {
40 countingSortByDigit(a, n, exp);
41 }
42}
43
44int main() {
45 int a[] = {170, 45, 75, 90, 802, 24, 2, 66};
46 int n = 8;
47
48 radixSort(a, n);
49
50 for (int i = 0; i < n; i++)
51 printf("%d ", a[i]);
52 // Output: 2 24 45 66 75 90 170 802
53 return 0;
54}Execution Example
Using [170, 45, 75, 90, 802, 24, 2, 66] as an example:
Round 1: Sort by ones digit
| Element | Ones Digit |
|---|---|
| 170 | 0 |
| 90 | 0 |
| 802 | 2 |
| 2 | 2 |
| 24 | 4 |
| 45 | 5 |
| 75 | 5 |
| 66 | 6 |
After sorting: [170, 90, 802, 2, 24, 45, 75, 66]
Round 2: Sort by tens digit
| Element | Tens Digit |
|---|---|
| 802 | 0 |
| 2 | 0 |
| 24 | 2 |
| 45 | 4 |
| 66 | 6 |
| 170 | 7 |
| 75 | 7 |
| 90 | 9 |
After sorting: [802, 2, 24, 45, 66, 170, 75, 90]
Round 3: Sort by hundreds digit
| Element | Hundreds Digit |
|---|---|
| 2 | 0 |
| 24 | 0 |
| 45 | 0 |
| 66 | 0 |
| 75 | 0 |
| 90 | 0 |
| 170 | 1 |
| 802 | 8 |
After sorting: [2, 24, 45, 66, 75, 90, 170, 802] -- Sorting complete!
MSD Radix Sort
MSD starts sorting from the most significant digit, then recursively sorts elements within each bucket by the next digit.
1#include <bits/stdc++.h>
2using namespace std;
3
4// Get the digit at position pos of x (counting from the highest digit, pos=0 is the highest)
5int getDigitMSD(int x, int pos, int maxDigits) {
6 int exp = 1;
7 for (int i = 0; i < maxDigits - 1 - pos; i++) exp *= 10;
8 return (x / exp) % 10;
9}
10
11void msdRadixSort(vector<int>& a, int pos, int maxDigits) {
12 if (a.size() <= 1 || pos >= maxDigits) return;
13
14 // Distribute into buckets by current digit
15 vector<vector<int>> buckets(10);
16 for (int x : a) {
17 int d = getDigitMSD(x, pos, maxDigits);
18 buckets[d].push_back(x);
19 }
20
21 // Recursively sort each bucket
22 for (auto& bucket : buckets) {
23 msdRadixSort(bucket, pos + 1, maxDigits);
24 }
25
26 // Collect results
27 int idx = 0;
28 for (auto& bucket : buckets) {
29 for (int x : bucket) {
30 a[idx++] = x;
31 }
32 }
33}
34
35int main() {
36 vector<int> a = {170, 45, 75, 90, 802, 24, 2, 66};
37
38 int maxVal = *max_element(a.begin(), a.end());
39 int maxDigits = 0;
40 while (maxVal > 0) { maxDigits++; maxVal /= 10; }
41
42 msdRadixSort(a, 0, maxDigits);
43
44 for (int x : a) printf("%d ", x);
45 // Output: 2 24 45 66 75 90 170 802
46 return 0;
47}LSD vs MSD Comparison
| Property | LSD | MSD |
|---|---|---|
| Direction | Low digit → High digit | High digit → Low digit |
| Implementation | Iterative, simpler | Recursive |
| Requires stable sort | Yes (critical) | Recursive within buckets is sufficient |
| Suitable scenarios | Integer sorting | String sorting, variable-length data |
| Space complexity | O(n + k) | O(n + k), additional recursion stack overhead |
| Common in competitions | More common | Less common |
Detailed Problem-Solving Steps
Decision process for using radix sort:
- Data is integers with a large range: Value range too large for counting sort, but radix sort works well when the number of digits is small
- Determine the base: Decimal is the most intuitive, but base 256 (per byte) or base 65536 can reduce the number of rounds
- Determine the sorting approach: Integers typically use LSD, strings use MSD
- Handle negative numbers: Add an offset to all numbers to make them non-negative, sort, then subtract the offset
Optimization tips for competitions: Use base 2^k (e.g., base 256), so digit extraction can use bit operations instead of division:
1void radixSort256(int a[], int n) {
2 int output[100005];
3 for (int shift = 0; shift < 32; shift += 8) {
4 int count[256] = {0};
5 for (int i = 0; i < n; i++)
6 count[(a[i] >> shift) & 0xFF]++;
7 for (int i = 1; i < 256; i++)
8 count[i] += count[i - 1];
9 for (int i = n - 1; i >= 0; i--) {
10 int d = (a[i] >> shift) & 0xFF;
11 output[--count[d]] = a[i];
12 }
13 for (int i = 0; i < n; i++) a[i] = output[i];
14 }
15}Common Mistakes
- Using an unstable sort for intra-bucket sorting: LSD radix sort requires each round's sort to be stable, otherwise results are incorrect
- Forgetting to traverse from back to front: Traversing from back to front in counting sort is key to ensuring stability
- Incorrect maximum digit count calculation: Failing to handle the special case of 0, or not including the highest digit
- Forgetting to handle negative numbers: Radix sort handles non-negative integers by default; negative numbers need extra handling
- Inappropriate base choice: Decimal requires only 10 buckets but more rounds; higher bases require fewer rounds but more buckets
Algorithm Evaluation
| Property | Radix Sort |
|---|---|
| Time Complexity | O(d * (n + k)), where d is the number of digits, k is the base |
| Space Complexity | O(n + k) |
| Stability | Stable (LSD version) |
| Applicable Conditions | Integers or fixed-length strings, with a limited number of digits |
When to choose radix sort:
- Integer sorting with a very large value range but limited digits (e.g., within 10^9, only 10 decimal digits)
- Need stable sorting with linear time
- Multi-key sorting in suffix array construction
Radix sort is less commonly used than sort in competitions, but it is an important optimization technique in specific scenarios (such as suffix arrays and large-scale integer sorting).