1. One-Liner
Radix Sort (LSD) sorts numbers digit by digit from least significant to most, using a stable subroutine (often counting sort) on each digit.
2. The Problem It Solves
Integers with fixed number of digits d and digit range [0, r-1] can be sorted in O(d · (n + r)) — linear when d is constant and r is small (e.g., bytes).
3. The Core Idea
Sort by last digit first (stable), then tens, then hundreds — like stacking sorts in a library: coarse order emerges as you refine from fine to broad.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. | Choose base r (e.g., 10 or 256) |
| 2. | For exponent p = 1, r, r², … until covers max value |
| 3. | Stable sort keys by digit (key / p) % r |
| 4. | After last digit pass, array is sorted |
5. Dry Run Example
Base 10: [170, 45, 75] — sort by ones, then tens, then hundreds — ends sorted.
6. Key Properties
| Property | Value |
|---|---|
| Stable passes required | Yes — LSD correctness |
| Non-comparison | Digit indexing |
| Strings | LSD works on fixed-width char codes |
7. Where It Is Used
| Company / System | How They Use It |
|---|---|
| Suffix arrays | Multi-key integer vectors |
| Database internals | Fixed-width codes |
8. Interview Tips
Contrast LSD vs MSD; why stability matters across passes; when radix beats comparison sorts.
9. Comparison with Other Algorithms
| Algorithm | Model | Typical |
|---|---|---|
| Radix | Digits | O(d(n+r)) |
| Quick | Comparison | O(n log n) |
10. Complexity
| Metric | Value |
|---|---|
| Time (Best) | O(d(n+r)) |
| Time (Average) | O(d(n+r)) |
| Time (Worst) | O(d(n+r)) |
| Space | O(n+r) per pass (counting) |
| Stable? | Yes (LSD with stable pass) |
Implementation Example (PYTHON)
def radix_sort(arr, r=10):
if not arr:
return arr
m = max(arr)
p = 1
while m // p > 0:
buckets = [[] for _ in range(r)]
for x in arr:
d = (x // p) % r
buckets[d].append(x)
arr = [x for b in buckets for x in b]
p *= r
return arr