Radix Sort

⚠️ This post was created when I was in high school and is no longer maintained.

1. Intuition

The algorithm works in a counterintuitive way: it sorts numbers by their least significant digit first, then by the next digit, and so on.

In order for radix sort to work correctly, the digit sorts must be stable.

In a typical computer, which is a sequential random-access machine, we sometimes use radix sort to sort records of information that are keyed by multiple fields. For example, we might wish to sort dates by three keys: year, month, and day. we could sort the information three times with a stable sort: first on day, next on month, and finally on year —— CRLS

From my point of view, using radix sort with counting sort as a subroutine mainly shrinks the k factor in T(n) (the bucket size) for the stable subroutine.

---

2. Pseudocode

algorithm RadixSort(A, d):
    For i := 1 to d do
        Use a stable sorting to sort A on digit i

---

3. Time complexity

Lemma 8.3 Given n d-digit numbers in which each digit can take on up to k possible values, RADIX-SORT correctly sorts these numbers in ` Θ(d(n+k)) ` time if the stable sort it uses takes Θ(n+k) time. — CLRS

4. Code

# Python
def extra_key(num, key_digit):
    radix = 10
    if key_digit == 1:
        return num % radix
    else:
        return num % (radix**key_digit) // (radix**(key_digit - 1))

def count_sort(array, array_buf, max_val, key_digit):
    counter = [0] * (max_val + 1)

    for i in range(len(array)):
        counter[extra_key(array[i], key_digit)] += 1
    for j in range(1, len(counter)):
        counter[j] += counter[j-1]
    for i in range(len(array)-1, -1, -1):
        array_buf[counter[extra_key(array[i], key_digit)]] = array[i]
        counter[extra_key(array[i], key_digit)] -= 1
    return array_buf[1:]

def radix_sort(array, digit_num):
    radix = 10
    for i in range(1, digit_num+1):
        array_buf = [0] * (len(array)+1)
        array = count_sort(array, array_buf, radix-1, i)
    return array

if __name__ == "__main__":
    array = [1034, 2240, 1400, 1000, 3498, 6537, 5263, 8628, 4567, 5888, 7777]
    print("Before sorting: ", array)

    print('After sorting: ', radix_sort(array, 4))