Explaining an algorithm with words is very challenging… sometimes code itself is much easier to understand.

Peeking the algorithm procedure was enough for me to implement the algorithm this time.

def radix_sort(arr: list[int]) -> list[int]:
    max_val = max(arr)

    # O(d) where d is the nuber of digits in the largest number
    digit: int = 1
    while digit < max_val:
        # O(1)
        bucket: list[list[int]] = []
        for i in range(10):
            bucket.append([])

        # O(n) where n is the number of elements in the input array
        for x in arr:
            bucket[x // digit % 10].append(x)

        # O(n)
        arr: list[int] = []
        for i in range(10):
            arr.extend(bucket[i])

        digit *= 10

    return arr


arr = [431, 256, 257, 843, 900, 23, 76, 0, 45]
print(f"{arr=}")
print(f"{radix_sort(arr)=}")  # [0, 23, 45, 76, 256, 257, 431, 843, 900]

Counting sort has a problem in its space complexity; we need an array with the size of the range of possible values to achive the super efficient time complexity O(n), where n is the number of elements in the input array.

Radix sort uses the counting sort in a limited way, only having a array with the size 10, while maintaining the order in each inner array.

Radix sort's time complexity is O(nd), where n is the number of elements in the input array to be sorted, and d is the digit of the largest number in the input array. And, the space complexity of the radix sort is O(n) because unlike the counting sort, we only need a limited size to leverage the counting/hashing logic.

Radix sort is stable, meaning it preserves the relative order of elements with equal keys (x quick sort o merge sort).

I better understand that the main advantage of radix sort is its non-comparision-based logic, making it very efficient when d, a fixed number of digits, is small, it can outperform O(nlogn). (When d is so small, can't we just use counting sort, then? It seems I need some experience…)

Sushi bowl 800 Yogurt 500 m&m's 300 Pasta 400 Sushi 700 Berries 300 Chips 400 Oats 200 Yogurt 500

20241109 ◎

Radix sort