Distribution sorts · Intermediate
Radix Sort
Stably group values by one digit at a time, usually from least significant to most.
- Best
- O(d(n + b))
- Average
- O(d(n + b))
- Worst
- O(d(n + b))
- Space
- O(n + b)
- Stability
- Stable
- Memory model
- Uses auxiliary storage
How it builds order
- Group by the ones digit using a stable pass.
- Collect buckets in digit order.
- Repeat for tens, hundreds, and so on.
- Stop after the most significant digit.
Why it works
Stability preserves the ordering established by less-significant digits while each new pass adds a higher-priority digit.
Watch for: Each digit pass must be stable so earlier digit order survives.
The interactive version of this page adds the full trace, synchronized pseudocode, practice decisions, input experiments, and mastery review.