Digit pass

Sort by each digit, starting from the least significant.

Digit pass

At each digit pass, we sort all elements by that digit. This is done with counting sort.

Since a digit ranges from 0 to 9, the range is k=10; counting sort is very fast. Each pass is O(n + 10) = O(n).

For d digits we do d passes; total O(dn).

Stable sub-sort

Radix sort works only if the sub-sorter is stable. If not, the order from previous passes is broken and the result is wrong.

Counting sort is stable by placing back to front. This makes it the natural choice for radix sort.

If the sub-sorter is not stable, radix sort cannot be used; each pass would destroy the previous sort.

Exercise Counting sort by digit

Write counting_by_digit(arr, d). Stably sort the array by digit d. Print [170, 90, 45, 75] with print(counting_by_digit([170, 45, 75, 90], 0)).

Show example solution

def get_digit(n, d):
    return n // (10 ** d) % 10
def counting_by_digit(arr, d):
    # Sort by digit d
    count = [0] * 10
    for x in arr:
        count[get_digit(x, d)] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    output = [0] * len(arr)
    for i in range(len(arr) - 1, -1, -1):
        digit = get_digit(arr[i], d)
        output[count[digit] - 1] = arr[i]
        count[digit] -= 1
    return output
print(counting_by_digit([170, 45, 75, 90], 0))

Test yourself

Digit range

k = ____  # range 0-9

Show answer

k = 10  # range 0-9

Digit pass: match the terms

Digit

0-9
Sub-sorter

Counting sort
Stable

Required
Pass

O(n)
Why does radix sort use counting sort?
- Less memory
- Easier
- Stable and fast
- Random
Show answer

Stable and fast — Stable and fast

Next lesson: Stable sub-sort

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies