Radix sort

Why this matters

Many lists hold numbers that have a fixed number of digits: ID numbers, postal codes, years, counts of items in a warehouse. For this kind of data there is a sorting method that does not compare two whole numbers at each step. It looks at one digit at a time. This method is called radix sort. The word "radix" means the base of a number system, and in this lesson the base is 10.

Most sorts you have seen so far compare two values and decide which one comes first. A comparison sort needs roughly n times log n comparisons in the worst case, and no comparison sort can do better than that for general values. Radix sort avoids that limit because it never asks "which of these two numbers is bigger?" It asks only "what is this digit?" When the numbers have a few digits each, the work grows in a straight line with the number of values.

This lesson covers non-negative whole numbers, which means zero and the positive numbers. The insertion sort lesson before this one counted steps on a sort that compares. Radix sort works in a different way, and the counting in this lesson is about passes and buckets rather than comparisons.

The idea: sort by the last digit first

Start with three numbers, 23, 11 and 32. Their first digits are 2, 1 and 3. If you sort by the first digit alone, you get 11, 23, 32, which is already correct. Now try 21, 13 and 12. Sorting by the first digit gives 12 and 13 in either order, then 21, and the last digits are not yet in order. Sorting by the last digit would then fix the other side. So which digit should you sort by first?

Radix sort answers this with a simple rule. It makes one pass for each digit place, starting from the last digit, which is the ones place. Each pass rearranges the whole list by one digit. The passes go in this order: ones, then tens, then hundreds, and so on. After the last pass the list is sorted.

Why does this work? Each pass must keep the order that the previous passes made when two values have the same digit in the current place. A pass that does this is called stable. A stable sort keeps two equal keys in the order they had before the sort. Here is a small case. Take the values 75 and 71. The ones pass puts 71 before 75, because 1 is less than 5. The tens pass sees that both values have a 7 in the tens place. A stable tens pass keeps 71 before 75, which is correct. An unstable one could swap them, giving 75 before 71, which is wrong. Because each pass is stable, the order made by the earlier passes is never lost. The last pass decides the big picture, and the earlier passes break the ties.

The bucket pass

A bucket pass does one digit place. It uses ten buckets, numbered 0 to 9, which are lists that hold values. The pass goes through the list from left to right. For each value, it finds the digit in the current place and adds the value to the end of that bucket. When every value is in a bucket, the pass reads the buckets in order, from bucket 0 to bucket 9, and writes the values back into the list.

Reading the buckets in order is what makes the pass correct. Values in bucket 0 end up first, values in bucket 1 come next, and so on. Inside one bucket, values stay in the order they came in, because the pass added them to the end of the bucket as it went. That is why the bucket pass is stable.

A worked example by hand

Take the list 170 45 75 90 802 24 2 66. It has 8 values and the largest value has three digits, so the sort needs three passes. The table shows each pass.

Look at the first pass closely. The ones digits, in the order of the input, are 0, 5, 5, 0, 2, 4, 2 and 6. The buckets collect values with those digits, and the values inside bucket 0 are 170 and 90 in that order, because 170 came before 90 in the input. After pass 1 the list is sorted by the ones digit only.

Look at pass 2. The values 170 and 75 both have a 7 in the tens place. Pass 1 had already put 170 before 75, and pass 2 keeps that order. Values with different tens digits are sorted by the tens digit. Within bucket 0, the values 802 and 2 keep the order that pass 1 gave them.

After pass 3 the list is sorted. Each value has been looked at for all of its digits, and each pass kept the order of the passes before it.

A short example with zeros

Look at the list 0 100 10 1000 5. The largest value is 1000, which has four digits, so there are four passes. A value like 5 has no tens, hundreds or thousands digit, which means those digits are 0. The bucket pass treats a missing digit as 0, so the value goes into bucket 0 in those passes. This is why the program does not need special handling for short numbers. A digit place that does not exist is just a 0.

Writing the code in C++

The program has two functions. The first, bucket_pass, does one pass. The second, radix_sort, runs passes until every digit place of the largest value has been used. Both take a std::vector<int> by reference, so they change the caller's list in place.

#include <algorithm>
#include <array>
#include <stdexcept>
#include <vector>
 
void bucket_pass(std::vector<int>& a, long long place) {
    std::array<std::vector<int>, 10> buckets;      // ten buckets, 0 to 9
    for (int x : a) buckets[(x / place) % 10].push_back(x);
    a.clear();
    for (const auto& b : buckets) a.insert(a.end(), b.begin(), b.end());
}
 
void radix_sort(std::vector<int>& a) {
    for (int x : a)
        if (x < 0) throw std::invalid_argument("radix_sort needs non-negative values");
    if (a.empty()) return;
    int biggest = *std::max_element(a.begin(), a.end());
    for (long long place = 1; biggest / place > 0; place *= 10)
        bucket_pass(a, place);
}

Here is what each part does.

The line std::array<std::vector<int>, 10> buckets; makes ten empty vectors. A std::array has a fixed size known at compile time, which is 10 here. Each element is a vector, so each bucket can grow as values arrive.

The expression (x / place) % 10 gives the digit. Take 802 with place equal to 10. Dividing 802 by 10 gives 80, because integer division drops the remainder. Then 80 % 10 gives 0, which is the tens digit of 802. For place equal to 100, 802 / 100 gives 8, and 8 % 10 gives 8, the hundreds digit. The variable place is the value of the digit place: 1 for ones, 10 for tens, 100 for hundreds, and so on.

The loop for (int x : a) goes through the list from start to finish, so values reach their buckets in their current order. The second loop reads the buckets from 0 to 9. The insert call adds all values of one bucket to the end of a, and it keeps their order.

In radix_sort, the first loop checks for negative values and throws an error if it finds one. This is explained in the mistakes section. The line if (a.empty()) return; handles an empty list, where there is nothing to find a largest value in. The std::max_element call returns an iterator, which is a pointer-like position in the list. The * in front of it reads the value at that position.

The loop for (long long place = 1; biggest / place > 0; place *= 10) runs one pass per digit place. It stops when biggest / place becomes 0. For biggest equal to 802, the places are 1, 10 and 100. At place 1000 the division gives 0, so the loop ends. The number of passes is therefore the number of digits in the largest value. A list whose largest value is 0 makes no passes, because 0 / 1 is 0 and the test fails at once. Such a list holds only zeros, so it is already sorted.

The variable place has type long long, not int. The reason is the last multiplication. If the largest value is near the top of the int range, the loop reaches place 1000000000, and the next place *= 10 would be 10000000000. That number is larger than an int can hold, and signed overflow is undefined behaviour in C++. A long long holds it without trouble.

Running it

The next program prints the list after each pass for the worked example, using the same functions. It then runs the zero example, the single-value example and the example with a three-digit list.

#include <iostream>
#include <vector>
 
void print(const std::vector<int>& a) {
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
}
 
// bucket_pass and radix_sort as above
 
int main() {
    std::vector<int> a = {170, 45, 75, 90, 802, 24, 2, 66};
    bucket_pass(a, 1);
    std::cout << "ones:     "; print(a);
    bucket_pass(a, 10);
    std::cout << "tens:     "; print(a);
    bucket_pass(a, 100);
    std::cout << "hundreds: "; print(a);
 
    std::vector<int> b = {0, 100, 10, 1000, 5};
    radix_sort(b);
    std::cout << "0 100 10 1000 5 -> "; print(b);
 
    std::vector<int> single = {9};
    radix_sort(single);
    std::cout << "single 9 -> "; print(single);
}

Compile and run it with these commands:

g++ -std=c++20 -Wall -o radix_demo radix_demo.cpp
./radix_demo

Output from g++ 15.2.0:

ones:     170 90 802 2 24 45 75 66 
tens:     802 2 24 45 66 170 75 90 
hundreds: 2 24 45 66 75 90 170 802 
0 100 10 1000 5 -> 0 5 10 100 1000 
single 9 -> 9 

The three pass lines match the table in the worked example. The last two lines show that the zero example and the single value both come out sorted.

A second example, with a few more numbers

Now try the list 13 8 21 100. It has three digit places in the largest value, so it has three passes. Here is the output of three calls to bucket_pass, with places 1, 10 and 100.

ones:     100 21 13 8 
tens:     100 8 13 21 
hundreds: 8 13 21 100 

Check the first pass. The ones digits are 3, 8, 1 and 0. Bucket 0 holds 100, bucket 1 holds 21, bucket 3 holds 13, and bucket 8 holds 8. So the first pass gives 100, 21, 13, 8. The second pass reads the tens digits, 0, 2, 1 and 0. The values 100 and 8 both have tens digit 0, and they keep their order from pass 1, so 100 comes before 8. The third pass reads the hundreds digits, 1, 0, 0 and 0. The three small values go to bucket 0 in the order they had, and 100 goes to bucket 1.

A third example, checking many lists

The third example checks the function against the standard std::sort on many random lists. This is the way to test a sort you have written. Generate many inputs, sort each one with both methods, and compare the results. The function std::sort is in the algorithm header and is trusted, so any difference is a bug in the new code.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <random>
#include <vector>
 
// bucket_pass and radix_sort as above
 
int main() {
    std::mt19937 rng(2026);
    int failures = 0;
    for (int trial = 0; trial < 2000; ++trial) {
        std::size_t n = rng() % 60;
        std::vector<int> v(n);
        for (auto& x : v) x = static_cast<int>(rng() % 100000);
        std::vector<int> expected = v;
        std::sort(expected.begin(), expected.end());
        radix_sort(v);
        if (v != expected) ++failures;
    }
    std::cout << "trials=2000 failures=" << failures << "\n";
 
    std::vector<int> big = {2147483647, 0, 1000000000, 7};
    radix_sort(big);
    for (int x : big) std::cout << x << ' ';
    std::cout << '\n';
}

Output:

trials=2000 failures=0
0 7 1000000000 2147483647 

The list of lengths runs from 0 to 59, so it includes the empty list. The big example includes the largest int value, 2147483647, which has ten digits. It needs 10 passes, and the long long place variable handles the last one without overflow.

Common mistakes

Reading the buckets in the wrong order

A common mistake is to read the buckets from 9 down to 0, instead of from 0 up to 9. The result is not an ascending sort. Here is the first pass on the worked example with the buckets read from 9 down to 0, and then the three passes for the digit places 1, 10 and 100 run that way.

after ones digit: 66 45 75 24 802 2 170 90
after all passes: 802 170 90 75 66 45 24 2

Every pass reverses the order of the buckets, so the final list runs from the largest value to the smallest. The sort still finishes, but in the wrong direction.

Stopping after one pass

A single pass sorts only by one digit. Running one pass on the worked example gives this:

170 90 802 2 24 45 75 66

Look at 170 and 2 in that list. The value 2 comes after 802 even though it is smaller. The list is not sorted until all the digit places are done. Make sure the loop runs until biggest / place is 0, and not just once.

Passing a negative number

Radix sort as written here handles only non-negative numbers. The digit of a negative number is found with %, and % on a negative value gives a negative result in C++. A negative bucket index would then reach past the end of the std::array, which is undefined behaviour. The function avoids this by checking first. Here is what happens when a negative value is passed in:

std::vector<int> neg = {3, -1, 2};
try {
    radix_sort(neg);
} catch (const std::invalid_argument& e) {
    std::cout << "caught: " << e.what() << "\n";
}

Output:

caught: radix_sort needs non-negative values

To sort negative numbers, a program can sort the negatives and the positives separately and join the results. That is outside the scope of this lesson.

Leaving out a template argument

When you first write the buckets, it is easy to leave out one of the two template arguments of std::array. Here is what g++ reports when the line is written as std::array<std::vector<int>> buckets;, with one template argument missing:

err_template.cpp:4:31: error: wrong number of template arguments (1, should be 2)
    4 |     std::array<std::vector<int>> buckets;
      |                               ^~

The compiler wants two arguments: the element type and the size. The fixed size is 10, so the correct line is std::array<std::vector<int>, 10> buckets;. Read the first line of a compiler error first, because it names the problem. The lines after it show where the compiler thinks the problem is.

Comparing a signed index with size()

A loop over the buckets or the list with an int index can give a warning. The size() function returns std::size_t, which is unsigned. Here is a loop that gives the warning:

for (int i = 0; i < a.size(); ++i) a[i] += 1;

g++ with -Wall prints this:

warn_sign.cpp:4:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]

Declare the index as std::size_t, or use a range-based loop as the bucket pass does, to remove the warning.

Forgetting that digits need a division

A common bug is to read the digit as x % place instead of (x / place) % 10. The first form gives the digits below the current place, not one digit. For 802 with place 100, 802 % 100 is 2, which is the remainder, not the hundreds digit 8. The correct form first divides by the place, which removes the lower digits, and then takes the remainder by 10, which keeps one digit.

Practice

Exercise 1. Sort 13 8 21 100 by hand, one pass at a time. Write the list after each pass.

Show the answer

Pass 1, ones digits 3, 8, 1, 0: the list becomes 100 21 13 8. Pass 2, tens digits 0, 2, 1, 0: the list becomes 100 8 13 21. Pass 3, hundreds digits 1, 0, 0, 0: the list becomes 8 13 21 100.

The result is sorted. The program prints the same three lines.

Exercise 2. How many passes does radix_sort make for each list: {9}, {0, 0} and {1000, 5}?

Show the answer

{9} makes one pass. The largest value is 9, and 9 / 1 is 9, which is more than 0. The loop then tries place 10, where 9 / 10 is 0, so it stops after one pass.

{0, 0} makes no passes. The largest value is 0, and 0 / 1 is already 0, so the loop body never runs. The list was sorted already.

{1000, 5} makes four passes, one for each place from 1 to 1000.

Exercise 3. The function bucket_pass must read the buckets from 0 to 9. Explain in plain words what goes wrong if the code adds each value to the front of its bucket instead of the back.

Show the answer

Adding to the front of a bucket reverses the order of the values that share a digit. Take the values 71 and 75, which are both in bucket 7 of the tens pass. Their order before the pass was 71 then 75. Adding to the front would store 75 then 71 in bucket 7, and the list would end with 75 before 71. The earlier passes had put 71 first, and that order would be lost. The sort would then not be stable, and the final list could be wrong.

Exercise 4. A programmer writes int place = 1; ... place *= 10; for a list whose largest value is 2147483647. Explain what can go wrong.

Show the answer

The loop runs for places 1, 10, 100, up to 1000000000. The last multiplication, place *= 10, computes 10000000000 in int, which is larger than the largest int, about 2.15 billion. Signed overflow is undefined behaviour in C++, so the program can do anything. The fix is to store place in a long long, as the code above does.

Exercise 5. The code below was meant to do one pass by the tens digit. Find the bug.

void tens_pass(std::vector<int>& a) {
    std::array<std::vector<int>, 10> buckets;
    for (int x : a) buckets[x % 10].push_back(x);
    a.clear();
    for (const auto& b : buckets) a.insert(a.end(), b.begin(), b.end());
}

Show the answer

The bug is x % 10, which gives the ones digit, not the tens digit. The fix is buckets[(x / 10) % 10], which first divides by 10 to remove the ones digit. With the input 13 8 21 100, the wrong code prints 100 21 13 8, which is the ones-digit order, while the correct tens pass prints 8 100 13 21. The bucket pass in this lesson avoids this kind of mistake by taking the digit place as a parameter, (x / place) % 10.

Summary

• Radix sort runs one stable bucket pass for each digit place, starting from the ones place.
• A bucket pass puts each value in the bucket for its digit, then reads the buckets from 0 to 9.
• The number of passes equals the number of digits in the largest value, so the work grows in a straight line with the number of values for a fixed number of digits.
• Use (x / place) % 10 to get a digit, and store the place in a long long so the last multiplication cannot overflow.
• This version handles non-negative values only. A negative value needs a separate method, and the function checks for one and throws an error.
• Test the function against std::sort on many random lists, because reading the buckets in the wrong direction still produces a finished list, just in the wrong order.