Radix Sort Algorithm

Radix Sort sorts integers digit by digit, using a stable subroutine such as Counting Sort for each digit position.

What is Radix Sort?

Radix Sort is a non-comparison sorting algorithm that sorts integers by processing their digits one position at a time. Instead of directly comparing two numbers, it groups numbers according to the digit currently being examined.

The most common version is LSD Radix Sort, where LSD means least significant digit. It starts from the ones digit, then moves to the tens digit, hundreds digit, and so on until all digit positions have been processed.

Core Intuition

Radix Sort works by sorting numbers one digit at a time. First, it sorts all numbers by their ones digit. Then it sorts them by their tens digit. Then it sorts them by their hundreds digit, and so on.

The crucial detail is stability. When two numbers have the same current digit, their previous order must be preserved. This is what allows the earlier digit-level ordering to remain useful as we move to more significant digits.

Radix Sort Algorithm Steps

1. Find the maximum value.
   The maximum value tells us how many digit positions must be processed.
2. Start with the ones place.
   Use exponent exp = 1 to extract the ones digit.
3. Stably sort by the current digit.
   Use Counting Sort or buckets so that equal digits keep their relative order.
4. Move to the next digit.
   Multiply exp by 10 to move from ones to tens, then hundreds.
5. Repeat until all digits are processed.
   Stop when max_num // exp == 0.
6. Return the sorted array.
   After the most significant digit pass, the whole array is sorted.

Interactive Radix Sort Visualization

Use the visualization below to see how Radix Sort groups numbers into digit buckets for the ones, tens, and hundreds places. The buckets are collected in order after every pass.

Dry Run Example

Suppose we want to sort:

[170, 45, 75, 90, 802, 24, 2, 66]

Pass 1: Sort by ones digit

• 170 has ones digit 0.
• 90 has ones digit 0.
• 802 and 2 have ones digit 2.
• 24 has ones digit 4.
• 45 and 75 have ones digit 5.
• 66 has ones digit 6.

After collecting buckets from digit 0 to 9:

[170, 90, 802, 2, 24, 45, 75, 66]

Pass 2: Sort by tens digit

Now sort the current array by tens digit while preserving the order from the ones-digit pass.

[802, 2, 24, 45, 66, 170, 75, 90]

Pass 3: Sort by hundreds digit

Now sort by hundreds digit:

[2, 24, 45, 66, 75, 90, 170, 802]

The array is now sorted.

Radix Sort Code in Python

This implementation uses Counting Sort as a stable subroutine for each digit. It assumes non-negative integers.

def radix_sort(arr):
    if not arr:
        return arr

    max_num = max(arr)
    exp = 1

    while max_num // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10

    return arr


def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    # Count occurrences of each digit.
    for num in arr:
        digit = (num // exp) % 10
        count[digit] += 1

    # Convert counts into prefix counts.
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Build output from right to left to keep the sort stable.
    for i in range(n - 1, -1, -1):
        digit = (arr[i] // exp) % 10
        count[digit] -= 1
        output[count[digit]] = arr[i]

    # Copy output back to arr.
    for i in range(n):
        arr[i] = output[i]


print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

Time and Space Complexity

When Should You Use Radix Sort?

Interview Notes and Common Pitfalls

This section highlights what interviewers usually expect you to understand about Radix Sort, especially its dependency on stable digit-level sorting.

What interviewers may expect you to know

• Radix Sort is not comparison-based.
• It sorts by digit positions rather than comparing whole numbers.
• LSD Radix Sort processes digits from least significant to most significant.
• Each digit pass must be stable.
• Counting Sort is commonly used as a stable subroutine.
• Its complexity depends on the number of digits and the base.

Common mistakes

• Using an unstable sort for each digit pass.
• Starting from the most significant digit, without changing the algorithm design.
• Forgetting that basic Radix Sort assumes integer-like keys.
• Ignoring negative numbers.
• Confusing value range with digit length.
• Claiming Radix Sort is always O(n) without explaining the digit factor.nd accidentally breaking stability.
• Claiming the algorithm is always better than O(n log n) without considering k.

Related coding interview problems

• Maximum Gap
• Sort an Array
• Relative Sort Array
• Top K Frequent Elements
• Sort Characters By Frequencys

Quick Quiz

Key Takeaways

• Radix Sort sorts numbers digit by digit.
• LSD Radix Sort starts from the least significant digit.
• Each digit pass must be stable.
• Counting Sort is commonly used as the stable digit-level sort.
• Its time complexity is O(d × (n + b)).
• It works best for integer-like values with bounded digit length.