Chapter 7: DSA Radix Sort
DSA Radix Sort – Let’s understand this one properly, like I’m sitting next to you with a whiteboard, explaining slowly, step-by-step, with multiple examples, visuals in words, code, and most importantly — when you should actually use it and why it’s very special.
What is Radix Sort?
Radix Sort is a non-comparison-based, integer sorting algorithm that can achieve linear time complexity under certain conditions.
The core idea is very clever:
Instead of comparing numbers with each other, we sort them digit by digit — starting from the least significant digit (rightmost) to the most significant digit (leftmost).
We use a stable sorting subroutine (usually Counting Sort) to sort the numbers based on each digit place one by one.
Because we go from right to left, the relative order built in previous passes is preserved — this is why stability is very important.
Two Main Versions
| Version | Starting from | Most common in teaching & interviews | Real-world usage |
|---|---|---|---|
| LSD Radix Sort | Least Significant Digit | ★★★★★ (almost always what is meant) | Very common |
| MSD Radix Sort | Most Significant Digit | Less common | Sometimes used |
We will focus on LSD (Least Significant Digit) Radix Sort — this is the standard one taught in DSA courses and asked in interviews.
How Radix Sort Works – Classic Example (step by step)
Numbers: 170, 45, 75, 90, 802, 24, 2, 66
Step 0: Find the maximum number 802 → has 3 digits → we will do 3 passes
Pass 1: Sort by units place (1’s digit)
|
0 1 2 3 4 5 6 7 |
170 45 75 90 802 24 2 66 0 5 5 0 2 4 2 6 ← units digit |
After stable sort on units place:
|
0 1 2 3 4 5 6 7 |
170 90 802 2 24 45 75 66 0 0 2 2 4 5 5 6 |
Pass 2: Sort by tens place (10’s digit)
|
0 1 2 3 4 5 6 7 |
170 90 802 2 24 45 75 66 7 9 0 0 2 4 7 6 ← tens digit |
After stable sort on tens place:
|
0 1 2 3 4 5 6 7 |
802 2 24 170 45 66 75 90 0 0 2 7 4 6 7 9 |
Pass 3: Sort by hundreds place (100’s digit)
|
0 1 2 3 4 5 6 7 |
802 2 24 170 45 66 75 90 8 0 0 1 0 0 0 0 ← hundreds digit |
After stable sort on hundreds place:
|
0 1 2 3 4 5 6 7 |
2 24 45 66 75 90 170 802 0 0 0 0 0 0 1 8 |
Final sorted array: 2, 24, 45, 66, 75, 90, 170, 802
Notice how the order is correct — and notice that numbers with the same digit in previous passes kept their relative order because we used stable sorting (Counting Sort) each time.
Visual Summary of Passes
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
Pass 0 (original): 170 45 75 90 802 24 2 66 After units: 170 90 802 2 24 45 75 66 After tens: 802 2 24 170 45 66 75 90 After hundreds: 2 24 45 66 75 90 170 802 |
Radix Sort Code – Most Common Interview Version (using Counting Sort)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
def counting_sort_for_digit(arr, exp): n = len(arr) output = [0] * n count = [0] * 10 # 0-9 digits # Count occurrences of current digit for i in range(n): digit = (arr[i] // exp) % 10 count[digit] += 1 # Change count[i] to position of last occurrence for i in range(1, 10): count[i] += count[i - 1] # Build output array (right to left → stable) i = n - 1 while i >= 0: digit = (arr[i] // exp) % 10 pos = count[digit] - 1 output[pos] = arr[i] count[digit] -= 1 i -= 1 # Copy back for i in range(n): arr[i] = output[i] def radix_sort(arr): if not arr: return arr # Find maximum number to know number of digits max_val = max(arr) # Do counting sort for every digit place exp = 1 while max_val // exp > 0: counting_sort_for_digit(arr, exp) exp *= 10 return arr # Example numbers = [170, 45, 75, 90, 802, 24, 2, 66] print("Before:", numbers) radix_sort(numbers) print("After: ", numbers) # Output: [2, 24, 45, 66, 75, 90, 170, 802] |
Time & Space Complexity (very important for interviews)
| Aspect | Complexity | Comment |
|---|---|---|
| Time | O(d × (n + k)) | d = number of digits, k = 10 (for decimal) |
| Space | O(n + k) | Usually O(n + 10) ≈ O(n) |
| Comparison-based | No | Uses digit extraction |
| Stable | Yes | Because we use stable Counting Sort |
| In-place | No | Needs extra array |
Simplified (for decimal numbers): O(d × n) where d is usually very small (3–10 for most practical numbers)
When to Use Radix Sort (Interview Answer – Must Know)
Use Radix Sort when:
- Numbers are integers (or can be treated as digit sequences)
- The number of digits (d) is small
- Range of values is large (10⁶–10⁹ or even bigger) — Counting Sort alone would need too much space
- You want linear or near-linear time sorting
- Stability is required
Real-world examples where Radix Sort shines:
- Sorting large lists of phone numbers
- Sorting postcodes / zip codes
- Sorting dates (year → month → day)
- Sorting strings of fixed length (when treated digit-by-digit)
- Sorting large datasets where values are bounded in digit length
- As part of suffix array construction in string algorithms
When NOT to use Radix Sort:
- Floating point numbers
- Very small arrays (n < 50–100) → Insertion Sort faster
- When most numbers have very different number of digits
- When memory is extremely tight (though it’s actually quite memory-friendly)
Quick Comparison Table
| Algorithm | Time (average) | Stable? | Space | Best Use Case |
|---|---|---|---|---|
| Radix Sort | O(d × n) | Yes | O(n) | Integers with small digit count |
| Counting Sort | O(n + k) | Yes | O(n + k) | Very small range (k << n) |
| Quick Sort | O(n log n) | No | O(log n) | General purpose |
| Merge Sort | O(n log n) | Yes | O(n) | Stability needed |
Summary – Radix Sort in one line each
- Non-comparison, digit-by-digit sorting
- Uses stable Counting Sort on each digit place (LSD: least significant first)
- Time complexity → O(d × n) where d is number of digits
- Very fast when number of digits is small
- Stable and linear time possible
- Perfect when sorting integers with bounded digit length
- One of the few algorithms that can beat O(n log n) in special cases
Do you want to go deeper into any related topic?
Natural next topics:
- How to handle negative numbers in Radix Sort
- MSD Radix Sort (most significant digit first)
- Radix Sort vs Counting Sort vs Bucket Sort
- Common interview questions on Radix Sort
- Sorting strings using Radix Sort idea
- How interviewers ask “Sort in linear time” questions
Just tell me which one you want next — I’ll explain it in the same detailed, human-teacher style! 😊
