DSA — Radix Sort

What is Radix Sort?

Sorts numbers digit by digit from least significant to most significant.

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    for num in arr:
        index = (num // exp) % 10
        count[index] += 1
    
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    i = n - 1
    while i >= 0:
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1
    
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_val = max(arr)
    exp = 1
    
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10
    
    return arr

Time Complexity

Case	Complexity
Best	O(d * (n + k))
Average	O(d * (n + k))
Worst	O(d * (n + k))

Where d is number of digits, k is base.

Characteristics

• Stable sort
• Not comparison-based
• Works with integers
• Good for fixed-length numbers

Mini Practice

1. Implement radix sort
2. Sort with different bases
3. Handle negative numbers
4. Compare with counting sort

Up Next

Continue with Bucket Sort — distribution-based sorting.