Radix Sort
Software Engineer path · lesson 15 of 99Sort integers digit by digit using a stable sort (like Counting Sort) as a subroutine. Achieves O(d×(n+b)) time where d is the number of digits and b is the base.
Whole numbers 0–9999. One pass per digit of the largest value.
Sort by the ones digit, then tens, then hundreds — each pass is stable.
- 1exp = 1
- 2while max(a) // exp > 0:
- 3 buckets = 10 empty lists
- 4 for x in a: buckets[(x // exp) % 10].append(x)
- 5 a = concatenate(buckets) # stable pass
- 6 exp *= 10
- Passes
- 0 / 3
- Moves
- 0 / 24
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
Least significant digit first
Order the passes of an LSD radix sort on three-digit numbers.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
- 5Drop a step here
Test your knowledge
Why must the per-digit sort in Radix Sort be stable?
The short version
Think of sorting a library by call numbers. First sort by the last digit, then the second-to-last, and so on. After processing all digits, the books are perfectly ordered!
In more depth
LSD Radix Sort (Least Significant Digit)
Process digits from right to left:
Why LSD Works
Later passes override earlier ones, but stable sorting ensures ties are broken by earlier digit order.
When to Use
When to reach for this
- Sorting large integers or fixed-length strings
- Need O(n) time for integer sorting
- Values have a fixed number of digits
- Sorting by multiple keys (like dates: year, month, day)
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required