Stable sub-sort

A stable sub-sort keeps previous passes intact.

Stable sub-sort

Full radix sort repeats the digit pass for every digit. It starts from the least significant and goes to the most significant.

Because each pass is stable, the order from the previous pass is preserved and the new digit adds information. At the end the array is fully sorted.

The digit count is d = len(str(max(arr))). Total cost O(dn).

Negative numbers

Radix sort by default sorts non-negative integers. For negative numbers there are two common methods.

First: add a fixed offset to all numbers to make them positive, sort, then subtract the offset. Second: split by sign and absolute value.

Both keep the O(dn) cost, but the implementation needs more care.

Exercise Radix sort

Write radix_sort(arr). Sort digit by digit with LSD. Print [2, 24, 45, 75, 90, 170] with print(radix_sort([170, 45, 75, 90, 2, 24])).

Show example solution

def get_digit(n, d):
    return n // (10 ** d) % 10
def counting_by_digit(arr, 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
def radix_sort(arr):
    # Sort digit by digit
    if not arr:
        return arr
    max_digits = len(str(max(arr)))
    for d in range(max_digits):
        arr = counting_by_digit(arr, d)
    return arr
print(radix_sort([170, 45, 75, 90, 2, 24]))

Test yourself

Stable sub-sort: match the terms

LSD

Start
Pass

Stable
Digit count

d
Total

O(dn)
How many passes does radix sort do?
- 1
- log n
- n
- d (digit count)
Show answer

d (digit count) — d (digit count)

Loop bound

for d in range(____):

Show answer

for d in range(max_digits):

Next lesson: Summary - Radix sort

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies