Radix Sort

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

1. Intuition

The algorithm working in a counterintuitive manner. It sorts the numbers on their lease significant digit first. Then, it sorts the numbers on their second significant digit next, 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

For my point of view, the main purpose of using the Radix sort that uses a counting sort as its subroutine is to reduce the k factor in the T(n) (the size of the bucket) of its 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))