🃏 Radix Sort

Intermediate ~12 min read

You have a deck of playing cards to sort. Instead of comparing every card, you have a clever strategy: Sort by suit first, then by rank. Or for numbers: Sort by ones digit, then tens, then hundreds. Each pass uses Counting Sort. That's Radix Sort - extending Counting Sort to larger ranges!

The Card Sorter

Imagine a machine with 10 buckets (0-9). Feed numbers through once for each digit position:

The Strategy (LSD - Least Significant Digit)

Pass 1: Sort by ones digit (rightmost) using Counting Sort
Pass 2: Sort by tens digit using Counting Sort
Pass 3: Sort by hundreds digit using Counting Sort
Continue: Until all digits processed
Result: Fully sorted!

Key insight: Each digit has small range (0-9), perfect for Counting Sort!

Extending Counting Sort

The Breakthrough

Counting Sort limitation: Only works for small ranges (like 0-100)

Radix Sort solution: Sort digit-by-digit!

Each digit: Small range (0-9) ✓
Multiple passes: d passes for d digits
Total time: O(d × n) - linear for fixed d!
Uses: Stable Counting Sort for each digit

See It in Action

Watch how Radix Sort processes each digit position:

Understanding the Process

Pass 1 (ones): Sort by rightmost digit
Pass 2 (tens): Sort by second digit (stable!)
Pass 3 (hundreds): Sort by third digit (stable!)
Each pass: O(n + k) where k=10
Total: O(d × n) for d digits
Stability crucial: Preserves previous sorting!

The Code

"""
Radix Sort - The Card Sorter
Sort digit-by-digit using stable Counting Sort!
O(d × n) linear time for fixed-length keys
"""

def radix_sort(arr):
    """
    LSD (Least Significant Digit) Radix Sort
    Time: O(d × n) where d = number of digits
    Space: O(n + k) where k = 10 (base)
    """
    if not arr or len(arr) <= 1:
        return arr
    
    print(f"Original array: {arr}")
    print(f"\n{'='*70}")
    print("LSD RADIX SORT - Sorting digit-by-digit (right to left)")
    print(f"{'='*70}")
    
    # Find maximum number to know number of digits
    max_num = max(arr)
    num_digits = len(str(max_num))
    
    print(f"Maximum number: {max_num}")
    print(f"Number of digits: {num_digits}")
    print(f"Number of passes needed: {num_digits}\n")
    
    # Do counting sort for every digit
    exp = 1  # 10^0 = 1 (ones), 10^1 = 10 (tens), etc.
    
    for digit_pos in range(num_digits):
        print(f"{'='*70}")
        print(f"PASS {digit_pos + 1}: Sorting by {get_digit_name(digit_pos)} digit")
        print(f"{'='*70}")
        
        # Show current digits
        print(f"\nCurrent state: {arr}")
        print(f"Digits at position {digit_pos}:")
        for num in arr:
            digit = (num // exp) % 10
            print(f"  {num:3d} → digit = {digit}")
        
        # Perform counting sort on this digit
        arr = counting_sort_by_digit(arr, exp)
        
        print(f"\nAfter sorting by {get_digit_name(digit_pos)} digit: {arr}\n")
        
        exp *= 10
    
    return arr

def counting_sort_by_digit(arr, exp):
    """
    Stable counting sort for a specific digit position
    exp: 1 for ones, 10 for tens, 100 for hundreds, etc.
    """
    n = len(arr)
    output = [0] * n
    count = [0] * 10  # Digits 0-9
    
    # Count occurrences of each digit
    for num in arr:
        digit = (num // exp) % 10
        count[digit] += 1
    
    print(f"\nCount array (how many of each digit): {count}")
    
    # Convert to cumulative counts (for stable sort)
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    print(f"Cumulative counts: {count}")
    
    # Build output array (right to left for stability)
    for i in range(n - 1, -1, -1):
        num = arr[i]
        digit = (num // exp) % 10
        output[count[digit] - 1] = num
        count[digit] -= 1
    
    return output

def get_digit_name(pos):
    """Get human-readable digit position name"""
    names = ["ones", "tens", "hundreds", "thousands", "ten-thousands"]
    return names[pos] if pos < len(names) else f"10^{pos}"

# Example 1: Basic Radix Sort
print("=" * 70)
print("Example 1: Basic Radix Sort")
print("=" * 70)
arr1 = [170, 45, 75, 90, 802, 24, 2, 66]
result1 = radix_sort(arr1.copy())
print(f"{'='*70}")
print(f"FINAL SORTED ARRAY: {result1}")
print(f"{'='*70}\n")

# Example 2: With duplicates
print("\n" + "=" * 70)
print("Example 2: With Duplicates")
print("=" * 70)
arr2 = [329, 457, 657, 839, 436, 720, 355, 457]
result2 = radix_sort(arr2.copy())
print(f"Final sorted: {result2}\n")

# Example 3: Already sorted
print("=" * 70)
print("Example 3: Already Sorted")
print("=" * 70)
arr3 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
result3 = radix_sort(arr3.copy())
print(f"Final sorted: {result3}\n")

# Example 4: Reverse sorted
print("=" * 70)
print("Example 4: Reverse Sorted")
print("=" * 70)
arr4 = [987, 654, 321, 210, 100]
result4 = radix_sort(arr4.copy())
print(f"Final sorted: {result4}\n")

# Example 5: Single digit numbers
print("=" * 70)
print("Example 5: Single Digit Numbers")
print("=" * 70)
arr5 = [9, 3, 7, 1, 5, 2, 8, 4, 6]
result5 = radix_sort(arr5.copy())
print(f"Final sorted: {result5}\n")

# Demonstrate why stability matters
print("=" * 70)
print("Example 6: Why Stability Matters")
print("=" * 70)
print("Sorting [12, 22, 32, 42] (all have same ones digit)")
print("\nWithout stability:")
print("  After ones sort: Could be [42, 32, 22, 12] (reversed!)")
print("  After tens sort: [12, 22, 32, 42] (correct by luck)")
print("\nWith stability (what we use):")
print("  After ones sort: [12, 22, 32, 42] (preserves order)")
print("  After tens sort: [12, 22, 32, 42] (correct!)")
print("\nStability ensures previous sorting is preserved!\n")

print("=" * 70)
print("Key Insights:")
print("=" * 70)
print("✓ Time: O(d × n) where d = number of digits")
print("✓ Space: O(n + k) where k = 10 (base)")
print("✓ Linear time for fixed-length keys!")
print("✓ Each pass uses stable Counting Sort")
print("✓ LSD: Simple, always d passes")
print("✓ Stability is CRUCIAL - preserves previous sorting")
print("✓ Perfect for: phone numbers, IDs, fixed-length integers")
print("✓ Extends Counting Sort to larger ranges!")

Output

Click Run to execute your code

Why Stability Matters: Without stable sorting, each pass would destroy the work of previous passes! After sorting by ones digit, numbers with the same tens digit must stay in order by ones digit. That's why we use stable Counting Sort!

Quick Quiz

Why does LSD Radix Sort start from the rightmost digit?

Show answer
Because of stability! After sorting by ones digit, all numbers ending in 0 are together, all ending in 1 are together, etc. When we sort by tens digit (stably!), numbers with the same tens digit stay in order by ones digit. This builds up the final sorted order digit by digit. Starting from the left (MSD) would require more complex recursive logic!
When would Radix Sort be slower than Quick Sort?

Show answer
When d (number of digits) is large! If sorting 64-bit integers (d=20 digits), Radix Sort is O(20n). Quick Sort is O(n log n) ≈ O(20n) for n=1M. They're comparable! But for variable-length or very large d, Quick Sort wins. Radix Sort is best for fixed-length keys with small d!

Why O(d × n)?

Let's break down the complexity:

Step	Time	Why
Find max (get d)	O(n)	One scan to find number of digits
Each pass	O(n + k)	Counting Sort for one digit (k=10)
Number of passes	d	One per digit position
Total	O(d × (n + k))	d passes × O(n + 10) each
Simplified	O(d × n)	Since k=10 is constant

✅ When is it Linear?

If d is constant (fixed-length keys):

Phone numbers: d=10 → O(10n) = O(n) ✓
SSN: d=9 → O(9n) = O(n) ✓
3-digit numbers: d=3 → O(3n) = O(n) ✓

Linear time for fixed-length keys!

When to Use Radix Sort

✅ Perfect For:

Phone numbers: Fixed 10 digits
Social Security numbers: Fixed 9 digits
IP addresses: Fixed 4 bytes
Fixed-length strings: Same length
Database integer keys: Bounded range

Rule of thumb: If d is small and fixed, Radix Sort wins!

❌ Avoid When:

Variable-length keys: Different d values
Large d: Many digits (64-bit integers)
Floating-point: Not integers
Need in-place: Radix needs O(n) space

Radix Sort vs Others

Feature	Counting Sort	Radix Sort	Quick Sort
Type	Non-comparison	Non-comparison ✓	Comparison
Time	O(n + k)	O(d × n) ✓	O(n log n)
Space	O(k)	O(n + k)	O(log n) ✓
Stable	Yes ✓	Yes ✓	No
Use When	Small range	Fixed-length ✓	General purpose

The Relationship

Radix Sort builds on Counting Sort:

Counting Sort: Single pass, small range only
Radix Sort: Multiple passes, extends to larger ranges!
Each Radix pass: Uses Counting Sort on one digit
Together: Complete the non-comparison sorting toolkit!

Common Misconceptions

❌ Misconception 1: "Radix Sort is always O(n)"

Reality: It's O(d × n) - depends on d!

Fixed d: O(n) ✓ (phone numbers, d=10)
Growing d: Not O(n)! (64-bit ints, d=20)
Variable d: Worst case dominates

Only linear for constant d!

❌ Misconception 2: "Radix Sort doesn't need stability"

Reality: Stability is CRUCIAL!

Without stability: Each pass destroys previous work
Example: [12, 22] sorted by tens → both have 1
If unstable: Could become [22, 12] after ones sort!
With stability: Preserves order, builds up sorting

Must use stable Counting Sort!

❌ Misconception 3: "Radix Sort is faster than Quick Sort"

Reality: Depends on d and n!

Small d: Radix wins (d=3: O(3n) vs O(n log n))
Large d: Quick wins (d=20: O(20n) vs O(n log n))
For n=1M: O(n log n) ≈ O(20n)
Crossover: Depends on constants and cache

Benchmark for your specific use case!

💡 Key Takeaway

Radix Sort is a powerful extension of Counting Sort:

✅ O(d × n) - linear for fixed-length keys
✅ Non-comparison - breaks O(n log n) barrier
✅ Stable - preserves order
✅ Perfect for phone numbers, IDs, fixed-length data
⚠️ Requires stability - must use stable Counting Sort
⚠️ Not for variable-length or large d

Understanding Radix Sort completes your non-comparison sorting toolkit!

Summary

The 3-Point Radix Sort Guide

Strategy: Sort digit-by-digit using stable Counting Sort - extends to larger ranges!
Complexity: O(d × n) - linear for fixed-length keys!
Trade-off: Speed for fixed-length vs limited to integers/strings

Interview tip: Mention Radix Sort for fixed-length integer keys. Explain digit-by-digit sorting, why stability is crucial, and when it beats comparison sorts!

What's Next?

You've mastered non-comparison sorting! Next: Tim Sort - the hybrid algorithm that powers Python and Java!

Practice: Implement Radix Sort for sorting phone numbers. Try both LSD and MSD approaches!

Previous Counting Sort

Next Tim Sort