Radix Sort

• uses counting sort as subroutine
• Used when element range is small
• Time: $O(d * (n + b))$, Space: $O(1)$
  • d -> total no of digits, b -> 10 (base))

Example:
319, 212, 6, 8, 100, 50
rewrite numbers with leading zero
319, 212, 006, 008, 100, 050
stable sort according to last digit (least significant digit)
100, 050, 212, 006, 008, 319
keep moving towards the most significant digit

Python

def countingSort(arr, exp):
    N = len(arr)    
    output = [0] * N
    count = [0] * 10
    for i in range(N):
        index = (arr[i] // 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 radixSort(arr):
    mx = max(arr)
    exp = 1
    while mx / exp > 1:
        countingSort(arr, exp)
        exp *= 10