Radix idea

Sort numbers digit by digit.

Radix idea

Radix sort sorts numbers digit by digit. First by the units digit, then tens, then hundreds... Each pass uses a stable sub-sorter (usually counting sort).

We start from the least significant digit (LSD) and move toward the most significant. Stability ensures the order from earlier passes is preserved.

With d digits and base k, the cost is O(d(n + k)). Effective even for large numbers.

LSD and MSD

LSD radix sort starts from the least significant digit. It re-sorts the whole array at each digit. Because it is stable, the final order is correct.

MSD radix sort starts from the most significant digit and splits each group recursively. It is more complex but may do fewer passes in some cases.

LSD is easier to implement and usually preferred.

Exercise Get digit

Write get_digit(n, d). Return digit d (0=units) of n. Print 3 with print(get_digit(738, 1)).

Show example solution

def get_digit(n, d):
    # Return digit d
    return n // (10 ** d) % 10
print(get_digit(738, 1))

Test yourself

Which sub-sorter does radix sort use?
- Quick sort
- Stable counting sort
- Heap sort
- Selection sort
Show answer

Stable counting sort — Stable counting sort

Digit count

d = len(str(____))

Show answer

d = len(str(max(arr)))

Radix idea: match the terms

LSD

Units first
MSD

Hundreds first
Sub-sorter

Counting sort
Cost

O(d(n+k))

Next lesson: Digit pass

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies