🌱 What Is Radix Sort?
Radix Sort is a non-comparative sorting algorithm — meaning it doesn’t compare numbers directly.
Instead, it sorts numbers digit by digit, starting from either the least significant digit (LSD) or the most significant digit (MSD).
Think of it like sorting a list of phone numbers:
You could first arrange them by the last digit, then by the second-last, and so on — until the whole list is perfectly ordered.
🧩 How Radix Sort Works (Step-by-Step)
Let’s understand this with an example:
We’ll sort [170, 45, 75, 90, 802, 24, 2, 66] in ascending order using LSD (Least Significant Digit) method.
Step 1: Sort by the rightmost digit (units place)
We group numbers according to their last digit:
| Digit | Numbers |
|---|---|
| 0 | 170, 90 |
| 2 | 802, 2 |
| 4 | 24 |
| 5 | 45, 75 |
| 6 | 66 |
| 8 | – |
| 9 | – |
After rearranging:[170, 90, 802, 2, 24, 45, 75, 66]
Step 2: Sort by the next digit (tens place)
Now we look at the second digit from the right:
| Digit | Numbers |
|---|---|
| 0 | 802, 2 |
| 2 | 24 |
| 4 | 45 |
| 6 | 66 |
| 7 | 75 |
| 9 | 90 |
| 7 | 170 |
After rearranging:[802, 2, 24, 45, 66, 75, 90, 170]
Step 3: Sort by the leftmost digit (hundreds place)
Now we sort based on the hundreds digit:
| Digit | Numbers |
|---|---|
| 0 | 2, 24, 45, 66, 75, 90 |
| 1 | 170 |
| 8 | 802 |
Final sorted list:[2, 24, 45, 66, 75, 90, 170, 802]
📊 Diagram of Radix Sort
Initial List: [170, 45, 75, 90, 802, 24, 2, 66]
Pass 1 (On units digit): [170, 90, 802, 2, 24, 45, 75, 66]
Pass 2 (On tens digit): [802, 2, 24, 45, 66, 75, 90, 170]
Pass 3 (On hundreds digit):[2, 24, 45, 66, 75, 90, 170, 802]Each pass brings the list closer to being fully sorted.
🧠 Why It Works
Radix Sort relies on stable sorting — meaning if two numbers have the same digit in the current position, their order stays the same as before.
That’s why we often use another algorithm like Counting Sort inside Radix Sort to handle each digit group efficiently.
💡 Real-Life Analogy
Imagine sorting a box of letters addressed to different cities.
You could first group them by the last letter of the city name,
then by the second last letter, and continue until they’re all neatly arranged.
That’s pretty much what Radix Sort does — but with digits!
⚙️ Time Complexity
- Best case: O(nk)
- Average case: O(nk)
- Worst case: O(nk)
Here,
- n = number of elements,
- k = number of digits in the largest number.
Radix Sort is very efficient when k is small compared to n.
🧾 Advantages
✅ Works great for large numbers or fixed-length integers.
✅ No comparisons needed between elements.
✅ Stable sorting (keeps order of equal elements).
⚠️ Disadvantages
❌ Needs extra space for temporary buckets or queues.
❌ Not suitable for data with very large digit counts or decimals.
About the Author
