Radix sort in Python

Why this matters

Most sorting methods compare two values at a time and ask which one is bigger. Unlike comparison sorts, radix sort never asks which of two values is bigger. It looks at one digit at a time, sorts the whole list by that digit, and repeats for the next digit. When the numbers have a small, fixed number of digits, this takes a fixed number of passes over the list, and each pass is a simple sweep.

Radix sort is useful for large lists of whole numbers, such as IDs, zip codes stored as numbers, or counts of items. It is also a good example of a general idea: a sort that is built from many simpler sorts, where each simpler sort must keep the work of the earlier ones. This lesson builds the method from a small example, shows the passes with real output, and then writes the Python code.

Each single pass here is a bucket pass, which is close to the bucket step in the counting sort lesson in this module. Radix sort repeats that pass once for each digit.

Terms used in this lesson

A digit is one symbol in a number written in base 10, such as 7 in 472. Base 10 means there are ten digit symbols, 0 to 9.

A place value is the power of 10 that a digit stands for. In 472, the 4 is in the hundreds place, the 7 is in the tens place, and the 2 is in the ones place. In code, place values are 1, 10, 100, and so on.

A bucket is a holding spot for values that share something. Here there are ten buckets, one for each digit from 0 to 9. In Python, a bucket is a list.

A pass is one full sweep of the list. In radix sort, each pass sorts the whole list by one digit.

Stable means that values which are equal under the sort keep the order they had before the sort. In radix sort, values with the same digit keep their order from the previous pass. Stability is the reason the method works, and the lesson shows an example where it breaks.

LSD stands for least significant digit first. The least significant digit is the one with the smallest place value, which is the ones digit. This lesson uses LSD radix sort, which starts with the ones digit and moves toward the largest digit.

A queue is a line where the first item added is the first item removed. A bucket that gets values at its end and gives them out from its front is a queue. The buckets in this lesson are queues, which is why the order inside each bucket is kept.

The idea: sort by one digit, then by the next

Start with a small list: [170, 45, 75, 90, 2, 802, 24, 66]. Do not try to sort the whole numbers. Sort by the ones digit first.

Put each number into the bucket that matches its ones digit, in the order the numbers come. Then read the buckets from 0 to 9 and write the numbers back into the list.

• The ones digit of 170 is 0, so it goes in bucket 0.
• The ones digit of 45 is 5, so it goes in bucket 5.
• The ones digit of 75 is 5, so it goes in bucket 5 after 45.
• The ones digit of 90 is 0, so it goes in bucket 0 after 170.
• The ones digit of 2 is 2, so it goes in bucket 2.
• The ones digit of 802 is 2, so it goes in bucket 2 after 2.
• The ones digit of 24 is 4, so it goes in bucket 4.
• The ones digit of 66 is 6, so it goes in bucket 6.

Reading the buckets from 0 to 9 gives 170, 90, 2, 802, 24, 45, 75, 66. The list is now sorted by its ones digit. Within the 0 bucket, 170 is still before 90, which is the order they had before.

The second pass sorts by the tens digit. The tens digit of 170 is 7, the tens digit of 90 is 9, and the tens digit of 2 is 0. Put each value into the bucket for its tens digit, in the current order, and read the buckets again. After this pass the list is sorted by its last two digits.

The third pass sorts by the hundreds digit. After that pass the list is in full order.

The key point is the order inside each bucket. A value that comes first in the current list stays first inside its bucket. So after the tens pass, numbers with the same tens digit keep the order they got from the ones pass. Their ones digits are already in order, so the result is sorted by the last two digits.

Getting a digit out of a number

Python has two operators that give a digit. Integer division, written with //, drops the part after the decimal point. The remainder operator, written with %, gives what is left after dividing. Together they pick out any digit.

For the digit at place value place, the code is (value // place) % 10. Here is how it works for 170 and place value 10. The division 170 // 10 gives 17. Then 17 % 10 gives 7, which is the tens digit.

The same formula gives the other digits. For the ones digit, use place value 1, which gives (170 // 1) % 10, so 0. For the hundreds digit, use 100, which gives (170 // 100) % 10, so 1.

Worked example 1: the classic list, pass by pass

The next program runs radix sort on the classic list and prints the list after each pass. The function digit_pass does one pass, and radix_sort_traced runs the passes. The data is built in, so you can run it without typing input.

The output is:

start      [170, 45, 75, 90, 2, 802, 24, 66]
pass 1 (   1) [170, 90, 2, 802, 24, 45, 75, 66]
pass 2 (  10) [2, 802, 24, 45, 66, 170, 75, 90]
pass 3 ( 100) [2, 24, 45, 66, 75, 90, 170, 802]
sorted     [2, 24, 45, 66, 75, 90, 170, 802]

The first pass matches the hand work above. Pass 2 sorts by the tens digit. The value 2 has tens digit 0, so it comes first, then 802 (tens digit 0), then 24 (tens digit 2). Pass 3 sorts by the hundreds digit. Values with hundreds digit 0 come first, which are 2, 24, 45, 66, 75 and 90, in the order they had after pass 2.

The loop stops after three passes. The largest value is 802, which has three digits. The loop condition biggest // place > 0 is true for place values 1, 10 and 100, and false for 1000, because 802 // 1000 is 0. So the number of passes equals the number of digits in the largest value.

Why the earlier passes must keep their order

The method depends on stability, so this section shows what happens without it. Take the list [13, 23, 11, 21, 12]. All of these values have a ones digit and a tens digit, and some share the same tens digit. The correct answer is 11, 12, 13, 21, 23.

Run the same two passes, but make each bucket a stack. A stack is a pile where the last item added is the first item removed. The code adds to the front of each bucket and removes from the front, which is last in, first out. This is the broken version. The only change from the working code is that each value is put at the front of its bucket with insert(0, value) instead of at the end with append.

The output of the broken version is shown here:

queue buckets  [11, 12, 13, 21, 23]
stack buckets  [13, 12, 11, 23, 21]

The stack version is wrong. In the tens pass, 13, 12 and 11 all have tens digit 1. They should keep the order they had after the ones pass, which put 11 and 12 before 13 in that bucket. The stack reverses them, so 13 comes out first. The result is not sorted.

The queue version keeps the order. Here is the queue version traced by hand. After the ones pass, the list is 11, 21, 12, 13, 23. In the tens pass, the values with tens digit 1 are 11, 12 and 13, and they come out in that same order. The values with tens digit 2 are 21 and 23. The result is 11, 12, 13, 21, 23.

This is why every pass must use a stable bucket pass. A pass that is not stable undoes the work of the earlier passes for values that share a digit.

Why the passes start at the ones digit

It might seem natural to start with the largest digit, since that is how people read numbers. That order does not work with this method, because the last pass decides the main order of the list. Whatever the last pass sorts by becomes the main order of the list.

If the last pass sorts by the ones digit, the list ends up in ones-digit order, and the tens digits do not count. So the last pass must be the largest digit, and each earlier pass only breaks ties for the digits that come after it. Starting from the ones digit and moving up makes each new pass the most important one so far, and stability keeps the earlier order for ties.

Writing the sort in Python

The code below is the full method. It writes the values back into the same list, so the caller sees the result. The buckets are plain lists, because append adds at the end and the loop reads the buckets from the front, which keeps the queue order.

def digit_pass(a, place):
    buckets = [[] for _ in range(10)]
    for value in a:
        digit = (value // place) % 10
        buckets[digit].append(value)
    k = 0
    for bucket in buckets:
        for value in bucket:
            a[k] = value
            k += 1
 
def radix_sort(a):
    biggest = max(a, default=0)
    place = 1
    while biggest // place > 0:
        digit_pass(a, place)
        place *= 10

The function radix_sort finds the largest value, then runs one pass for each place value while the place value fits inside that largest value. The argument default=0 makes max return 0 for an empty list, so the loop does not run and the empty list is returned unchanged. A list with one value also works. If that value is 1 or more, the loop runs once for the ones digit and leaves the value in place. If it is 0, the loop runs no passes.

The function digit_pass does the work of one pass. It creates ten buckets. It loops over the values in the current order, computes the digit, and adds the value to the end of that digit's bucket. Then it reads the buckets from 0 to 9 and writes the values back into the list. The variable k is the next free index in the list.

The function does not create a new list for the result. It writes back into the same list after each pass. During a pass the buckets hold every value once, so the extra memory is about the size of the list.

The cost in plain words

Each pass visits every value once when it puts values into buckets, and once when it reads them back. It also visits the ten buckets. So one pass costs about n plus 10 steps, where n is the number of values. The number of passes equals the number of digits in the largest value. Call that number d. The total work is about d times n plus 10 d.

For a list of 100,000 values where each value has at most 10 digits, this is at most 10 passes of about 100,000 steps each. The work grows in a straight line with the list length. Compare this with insertion sort on reversed data, where the work grows with the square of the list length.

Radix sort is not always faster. It works well when the number of digits is small compared with the list length. For a list of 3 values with 10 digits each, a comparison sort does less work. The formula above shows the reason: the number of passes is set by the digits, not by the list length.

Worked example 2: a list with many digit lengths

This example checks that the method handles numbers with different numbers of digits. Take the list [38, 7, 120, 5]. The largest value is 120, which has three digits, so there are three passes. The trace below follows the same code as the first example.

Pass 1 uses the ones digit. The values are 38 (ones digit 8), 7 (7), 120 (0) and 5 (5). The buckets are 0: 120, 5: 5, 7: 7, and 8: 38. The list becomes 120, 5, 7, 38.

Pass 2 uses the tens digit. The values are 120 (tens digit 2), 5 (tens digit 0), 7 (tens digit 0) and 38 (tens digit 3). The buckets are 0: 5 and 7, 2: 120, 3: 38. The list becomes 5, 7, 120, 38.

Pass 3 uses the hundreds digit. The values are 5 (0), 7 (0), 120 (1) and 38 (0). The buckets are 0: 5, 7 and 38, and 1: 120. The list becomes 5, 7, 38, 120.

The next program prints the list after each pass, and it matches the hand trace. A value with fewer digits is treated as if it had zeros in front. The value 5 has tens digit 0 and hundreds digit 0, so it lands in bucket 0 in both of those passes. In the hundreds pass, the values 5, 7 and 38 all go to bucket 0, and they keep their order from the tens pass, which is 5, 7, 38. That order is correct, so the stability rule and the leading zeros work together.

The output is:

[120, 5, 7, 38]
[5, 7, 120, 38]
[5, 7, 38, 120]

Worked example 3: 100,000 random values

The next program checks the method on a list that is much larger than the examples. It creates 100,000 random values from 0 up to, but not including, 2,147,483,647, which is the largest 32-bit signed integer. It sorts a copy with Python's sorted(), sorts the original with radix sort, and compares the two. The seed value is fixed, so the same numbers come out on every run.

The output is:

matches sorted: True
first five: [12675, 19884, 38070, 102900, 129966]
last five: [2147421248, 2147437339, 2147454712, 2147466672, 2147480389]

The result matches the built-in sort. The largest value in this list has ten digits, so the loop uses place values from 1 up to 1,000,000,000, which is ten passes. A useful test for a sort of your own is to compare its output with a trusted sort on random data, with several list sizes.

Common mistakes

Passing negative numbers. Radix sort in this lesson works only for numbers that are zero or bigger. Python's // and % round toward negative infinity, so the digits of a negative number do not look the way they do on paper. For -5, -5 // 10 is -1 and -5 % 10 is 5. The digit of -5 is treated as 5, and no error appears. The output is wrong, and nothing in it shows why. This is the most dangerous kind of bug in this lesson. The next program runs radix sort on a list with a negative number:

The output is:

negative input: [3, 12, -5]
5 -1

The list is not sorted, and -5 ends up last. The second line shows why: Python gives the digit of -5 as 5, which is the same digit as the number 5, and -5 // 10 is -1. To sort negative numbers, sort the non-negative and negative values separately, or add an offset to every value first so that the smallest value becomes zero. The offset method is short, but it is a separate topic, so this lesson does not use it.

Using a loop test that is too long or too short. The loop must stop after the last digit of the largest value. A test such as while place <= 10 ** 9 runs a fixed number of passes, and it does extra work on short numbers. The test biggest // place > 0 stops as soon as the place value is bigger than the largest value, so it works for any list.

Making the buckets stacks instead of queues. The stability section above showed the output of a stack version. The code change is small. Using insert(0, value) instead of append(value) looks harmless, and the code still runs and prints a list. The list is not sorted. Keep the rule: add to the end of each bucket and read from the front.

Starting from the largest digit. Sorting by the tens digit first and the ones digit last gives the wrong order. The last pass sets the main order, so the largest digit must go last. Use the order given in this lesson: ones first, then tens, then hundreds.

Forgetting to write back into the list. Each pass fills the buckets and reads them into the list. If a pass fills the buckets and then forgets the read-back loop, the list is unchanged and the next pass uses the old order. The sort then returns a wrong result without any error message. Always check the output of each pass when you write a new version.

Assuming an empty list works the same way as a list with values. The function max raises an error on an empty list unless you pass default. The version in this lesson uses max(a, default=0), so an empty list returns at once. If you leave out default, Python raises a ValueError. In Python 3.14 the message is max() iterable argument is empty, and older versions word it differently.

Expecting a limit on the size of the numbers. Python integers have no fixed size, so the place value can grow past 1,000,000,000 without wrapping around. In Java, the same loop with an int place value overflows, and the place values stop being powers of ten. Python does not have that problem, because the place value stays exact. The loop still stops at the right time, because it depends on the largest value.

Practice

Try each exercise in a file first. Check your answer after you have made an attempt.

Exercise 1. Trace radix sort on [38, 7, 120, 5] by hand. Write the list after each of the three passes.

Show the answer

After pass 1 (ones digit): 120, 5, 7, 38. After pass 2 (tens digit): 5, 7, 120, 38. After pass 3 (hundreds digit): 5, 7, 38, 120. The program in worked example 2 prints the same three lists.

Exercise 2. How many passes does radix sort make on [999, 1000]? Explain your answer in terms of the largest value.

Show the answer

It makes 4 passes. The largest value is 1000, which has four digits. The loop runs for place values 1, 10, 100 and 1000, and stops when the next place value, 10000, is bigger than the largest value. The result is [999, 1000].

Exercise 3. Take the list [31, 13, 33, 11]. Predict the list after two passes with stack buckets (each value added to the front of its bucket). Then predict the list after two passes with queue buckets. Explain which one is sorted.

Show the answer

With stack buckets the result is [13, 11, 33, 31]. With queue buckets the result is [11, 13, 31, 33], which is sorted. The stack version reverses the order of values that share a digit, so the second pass undoes part of the first.

Exercise 4. What is the tens digit of 4071? What is the hundreds digit? Use the formula (value // place) % 10 and show each step.

Show the answer

The tens digit is 7. The division 4071 // 10 gives 407, and 407 % 10 gives 7. The hundreds digit is 0. The division 4071 // 100 gives 40, and 40 % 10 gives 0.

Exercise 5. A friend says the buckets in digit_pass can be plain arrays of numbers with a fixed size instead of lists. Explain what the friend must add to keep the order inside each bucket, and why the list version does not need that extra work.

Show the answer

The friend must first count how many values fall in each bucket, then work out where each bucket starts in a new output array, and then place each value in its slot while walking the input from the start. That is the counting approach from the counting sort lesson, and it needs a second array the same size as the list. The list version does none of this counting. append adds each value to the end of its bucket, and the loop reads the buckets from the front, so the arrival order is kept.

Exercise 6. Radix sort the list [5, 0, 10] by hand, then check the answer with the program.

Show the answer

Pass 1 (ones): bucket 0 holds 0 and 10, bucket 5 holds 5. The list becomes [0, 10, 5]. Pass 2 (tens): bucket 0 holds 0, 5 and bucket 1 holds 10. The list becomes [0, 5, 10]. The result is sorted.

Summary

• Radix sort sorts whole numbers by one digit at a time, starting from the ones digit and moving toward the largest digit.
• Each pass must be stable, so values that share a digit keep the order they had from the earlier passes.
• The number of passes equals the number of digits in the largest value, and each pass costs about the list length plus 10.
• Use // and % to read a digit, and use only non-negative values unless you add a separate step for negative numbers.
• Python does not overflow on large numbers, but a negative number gives a wrong answer without an error.
• Test the method against sorted() on random data, since a wrong pass can give an answer that looks almost right.