Radix Sort - Code

Here is the implementation of radix sort:

function radixSort(arr):
    maxVal = max(arr)
    exp = 1
    while maxVal / exp >= 1:
        countingSortByDigit(arr, exp)
        exp = exp * 10

function countingSortByDigit(arr, exp):
    n = arr.length
    output = array of size n
    count = array of size 10, all zeros

    for i from 0 to n-1:
        digit = (arr[i] / exp) mod 10
        count[digit] = count[digit] + 1

    for i from 1 to 9:
        count[i] = count[i] + count[i-1]

    for i from n-1 down to 0:
        digit = (arr[i] / exp) mod 10
        output[count[digit] - 1] = arr[i]
        count[digit] = count[digit] - 1

    copy output to arr

Time: $O(d \cdot (n + k))$ where $d$ is the number of digits and $k$ is the base (10 for decimal).

Space: $O(n + k)$ (excluding input array).