Radix Sort

Table of Contents +

Say you have a big list of numbers. You want them sorted. Most sorting methods compare numbers against each other, again and again. Radix Sort does something different. It never compares two whole numbers. Instead it looks at them one digit at a time. So let us see how that works and why everything still ends up in the right order.

Radix Sort is a sorting method that orders numbers by looking at their digits one place at a time, from the rightmost digit to the leftmost.

🎯 The Problem First

Comparison sorts ask the same question over and over. “Is this number bigger than that one?” For a long list that is a lot of questions. But for numbers we already know something useful. A number is just a string of digits. If we line up the digits the right way, the order falls out on its own. No big comparisons needed.

That is the idea Radix Sort uses. It sorts by digit position instead of by comparing full values.

📚 A Real-World Analogy

Think about sorting a stack of paper forms. Each form has a phone number on it.

You could compare every pair of phone numbers. That is slow and tiring. So instead you do this:

  • First make piles based on the last digit. Pile 0, pile 1, all the way to pile 9.
  • Stack the piles back up in order.
  • Now make piles based on the second-to-last digit.
  • Stack them up again.
  • Keep going until you reach the first digit.

After the last round, the whole stack is sorted. That is exactly how Radix Sort works.

🔢 Why Start From the Last Digit?

This part confuses people, so let us go slow. We start from the least significant digit. That is the rightmost digit, the ones place.

Here is the idea:

  • The leftmost digit matters most. But we sort by it last.
  • Each round must keep the order from the round before it.
  • A sort that keeps the earlier order for equal items is called a stable sort.

So when we sort by the tens digit, two numbers with the same tens digit stay in the order the ones round already gave them. By the time we sort the biggest digit, all the smaller digits are already arranged underneath. The order just clicks into place.

Caution

The inner sort used in each round must be stable. If it shuffles equal items around, the earlier rounds are wasted and the final result is wrong. Counting sort is a common stable choice.

🧭 A Small Trace

Let us sort this list: [170, 45, 75, 90, 802, 24, 2, 66].

The biggest number has 3 digits, so we do 3 rounds: ones, tens, hundreds. Numbers with fewer digits are treated as if the missing places are 0.

Round Sort by Result order
Start — 170, 45, 75, 90, 802, 24, 2, 66
1 ones digit 170, 90, 802, 2, 24, 45, 75, 66
2 tens digit 802, 2, 24, 45, 66, 170, 75, 90
3 hundreds digit 2, 24, 45, 66, 75, 90, 170, 802

See how everything is in order after the last round? Each round only looked at one digit. Yet the full list came out sorted.

🪜 Steps to Do Radix Sort

Here is the plan we will turn into code:

  1. Find the largest number in the list. This tells us how many digits we must process.
  2. Start at the ones place. Set a place value of 1.
  3. Sort the list by the current digit using a stable counting sort.
  4. Move to the next digit by multiplying the place value by 10.
  5. Repeat until the place value passes the largest number.
  6. The list is now fully sorted.

The helper inside each round is counting sort. But we only count the single digit at the current place. We pull that digit out with (number / place) % 10.

💻 Radix Sort in Code

This code sorts a list of non-negative integers. It runs one counting-sort pass per digit, from the ones place upward, then prints the result.

radix_sort.py
def counting_sort_by_digit(arr, place):
    n = len(arr)
    output = [0] * n
    count = [0] * 10


    # Count how many numbers have each digit (0-9) at this place
    for num in arr:
        digit = (num // place) % 10
        count[digit] += 1


    # Turn counts into positions
    for i in range(1, 10):
        count[i] += count[i - 1]


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


    return output




def radix_sort(arr):
    max_value = max(arr)
    place = 1
    # One pass per digit, moving the place value up by 10 each time
    while max_value // place > 0:
        arr = counting_sort_by_digit(arr, place)
        place *= 10
    return arr




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

The output of the above code will be:

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

Note

Notice the inner loop runs from the last item to the first. That right-to-left order is what keeps the counting sort stable. So each digit round respects the order of the round before it.

⏱️ How Fast Is It?

Let us name the parts first so the formula makes sense:

  • n is how many numbers are in the list.
  • d is how many digits the largest number has.
  • k is the range of one digit, which is 10 for normal base-10 numbers.

Each digit round is one counting sort. That costs about n + k work. We do d rounds. So the total time is O(d * (n + k)).

Tip

When d is small and the numbers are not huge, O(d * (n + k)) behaves almost like O(n). That is why Radix Sort can beat comparison sorts on large lists of fixed-size integers.

Here is the full picture:

Case Time Space
Best O(d * (n + k)) O(n + k)
Average O(d * (n + k)) O(n + k)
Worst O(d * (n + k)) O(n + k)

⚠️ Common Mistakes

A few traps catch people the first time:

  • Using an unstable inner sort. If equal digits get reordered, the earlier rounds break and the final list is wrong.
  • Starting from the most significant digit by mistake. The simple version here works from the rightmost digit, not the leftmost.
  • Forgetting negative numbers. This basic version only handles non-negative integers. Negatives need extra handling.
  • Counting the wrong digit. The digit at a place comes from (number / place) % 10, not from the raw number.

🧩 What You’ve Learned

  • ✅ Radix Sort orders numbers by looking at one digit at a time, never comparing whole values.
  • ✅ It starts from the least significant digit (the rightmost) and moves left.
  • ✅ Each round uses a stable sort, usually counting sort, so earlier order is kept.
  • ✅ The digit at a place is found with (number / place) % 10.
  • ✅ Its time is O(d * (n + k)), which is close to linear when the digit count d is small.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Which digit does Radix Sort process first?

    Why: Radix Sort starts at the rightmost digit and moves toward the leftmost, one place per round.

  2. 2

    Why must the inner sort used each round be stable?

    Why: A stable sort preserves the earlier order for equal items, which is what makes the digit-by-digit approach end up correct.

  3. 3

    How do you extract the digit at a given place value?

    Why: Dividing by the place value drops the lower digits, then % 10 keeps just the digit at that place.

  4. 4

    What is the time complexity of Radix Sort?

    Why: It does d rounds, and each round is a counting sort costing about n + k, giving O(d * (n + k)).

Score: 0 / 4

🚀 What’s Next?

Previous Counting Sort Next Sorting Algorithms Comparison

Share & Connect

Share on LinkedIn