Radix Sort: A C++ version

Question

Just realized I have never implemented Radix Sort (spurred about watching a YouTube video about it). So I thought I would give it a go.

This is Radix Sort, using a counting implementation. For numbers that are N bytes in length, we use an N pass counting approach. Starting with the least significant byte we do a counting sort of all the values. We then repeat the counting sort using each consecutively higher byte in the values as the index.

Only have access to C++17 (so added some view objects (that I believe are available in C++20).

Comment on anything appreciated.

Suggestions on how I could remove the final std::move() to remove that copy would be nice. If I was not using iterators, that would be trivial. I am sure I can do it with some thought.

Views

#include <iostream>
#include <vector>
#include <array>


// A normal and reverse view created from Iterators.
// Makes using the Range based `for()` easier rather than having
// to manually work with the iterators themselves.
template<typename I>
struct View
{
    I beginRange;
    I endRange;
    View(I beginRange, I endRange)
        : beginRange(beginRange)
        , endRange(endRange)
    {}
    using iterator = I;
    iterator begin() {return beginRange;}
    iterator end()   {return endRange;}
};
template<typename I>
struct ReverseView
{
    I beginRange;
    I endRange;
    ReverseView(I beginRange, I endRange)
        : beginRange(beginRange)
        , endRange(endRange)
    {}
    using iterator = std::reverse_iterator<I>;
    iterator begin() {return iterator(endRange);}
    iterator end()   {return iterator(beginRange);}
};

Radix Sort

template<typename I>
void rsort(I begin, I end)
{
    // Create an intermediate output container.
    using Type = typename std::iterator_traits<I>::value_type;
    std::vector<Type>               output(std::distance(begin, end));

    // A loop to loop over each byte as the radix index.
    for (int index = 0; index < sizeof(Type); ++index) {

        // Keep track of counts for each radix value.
        // Since we are using bytes we need 256 values 0->255
        std::array<std::uint64_t, 0x100>  count{};

        // Step 1: Count each radix value.
        // Complexity O(n)
        for (auto const& value: View(begin, end)) {
            ++count[  (value >> (index * 8)) & 0xFF ];
        }

        // Step 2: Calculate prefix value.
        // Effectively if we do a count sort this is the
        // one past the end of the range for this value
        // of radix to be stored.
        // Complexity O(1)   assuming 255 is small compared to n
        std::uint64_t sum = 0;
        for (auto& c: count) {
            sum = sum + c;
            c = sum;
        }

        // Step 3: Copy from the input to output by
        // using the radex index (do in reverse order).
        // Complexity O(n)
        for (auto const& value: ReverseView(begin, end)) {

            // Offset starts at one past the end of the
            // range for this radix value.
            std::uint64_t&  offset = count[ (value >> (index * 8)) & 0xFF ];

            // So subtract one before using.
            // It now becomes one past the end for the remaining
            // values in the input array for this count.
            --offset;
            output[offset] = value;
        }

        // Step 4: Copy output back to the input.
        //         I am sure I can eliminate this step with some thought.
        // Complexity O(n)
        std::move(std::begin(output), std::end(output), begin);
    }
}

So Complexity is O(4 * (3n + 1)) => O(12n + 4) => O(n).

A test harness:

int main()
{
    std::vector<int> data{4583,182,5433,8092,11465,6614,29731,24061,29432,24542,32685,9724,31005,456,29255,25325,30048,18875,27775,30360,13531,1029,5715,3729,31680,22998,2359,29525,15433,7106,20196,11561,20578,14325,231,6835,8729,22579,21733,21845,28353,25495,8623,32589,4329,24583,10505,22413,32000,28538,12858,12123,23749,25833,16723,7593,30064,11542,30528,3122,17570,1792,26256,31321,13,18465,26884,4544,25571,10349,16857,26795,31744,21003,6357,3603,21462,12498,6675,15242,14620,15746,18063,18642,32054,16583,16753,15675,24931,18926};

    rsort(std::begin(data), std::end(data));
    std::cout << "[ ";
    char sep = ' ';
    for (auto const& v: data) {
        std::cout << sep << " " << v;
        sep = ',';
    }
    std::cout << " ]\n";
}

The result:

[   13, 182, 231, 456, 1029, 1792, 2359, 3122, 3603, 3729, 4329, 4544, 4583, 5433, 5715, 6357, 6614, 6675, 6835, 7106, 7593, 8092, 8623, 8729, 9724, 10349, 10505, 11465, 11542, 11561, 12123, 12498, 12858, 13531, 14325, 14620, 15242, 15433, 15675, 15746, 16583, 16723, 16753, 16857, 17570, 18063, 18465, 18642, 18875, 18926, 20196, 20578, 21003, 21462, 21733, 21845, 22413, 22579, 22998, 23749, 24061, 24542, 24583, 24931, 25325, 25495, 25571, 25833, 26256, 26795, 26884, 27775, 28353, 28538, 29255, 29432, 29525, 29731, 30048, 30064, 30360, 30528, 31005, 31321, 31680, 31744, 32000, 32054, 32589, 32685 ]

Answer 1

In addition to JDługosz's answer:

Use std::size_t

Use it for index, as the value type of the array count, for sum and index. Using it for index avoids the comparison between signed and unsigned values, and since you can never count more elements than a std::size_t can hold, it's the perfect type for count. In fact, it will be more efficient that way on 32-bit architectures.

Use += where appropriate

Instead of sum = sum + c, write sum += c instead.

Consider making rsort() take a View as the argument

Especially if the caller already uses Views themselves, it would be nice to be able to pass that to rsort() instead of having to manually specify the begin and end iterator. There are several ways to do this and still allow separate begin/end iterators to be used by the caller. One is to just add an overload, the second way is to only have a version that takes a View:

template<typename I>
void rsort(View<I> view) {
    ...
}

And the caller can then still do something like:

std::vector<int> data{4583, 182, 5433, ...};
rsort({std::begin(data), std::end(data)});

This requires extra curly braces though. Another way is to add a copy constructor to View, and make rsort() take a parameter pack that is perfectly forwarded to the constructor of View:

template<typename I>
struct View
{
    View(const View &other) = default;

    View(I beginRange, I endRange)
        : beginRange(beginRange)
        , endRange(endRange)
    {}
    ...
};

template<typename... Args>
void rsort(Args&&... args) {
    View view(std::forward<Args>(args)...);
    ...
}

Of course now you have the problem that error messages due to incorrect arguments are not so nice, unless you add concepts.

Avoid step 4

There are several possible in-place radix sort algorithms that you could try to implement. There are also people who submitted their in-place radix sort to Code Review, like this one, that you can have a look at.

Answer 2

😀 First, it's good to see someone use iterator pairs and (somewhat) generic code, as opposed to the usual hard-coded collections being passed.

---

Your View templates define constructors which don't do anything that would not be automatic had you left that out. Having common data members for more than one class suggests you can use a common base class for the data, to propagate the convention. (Given only these two views, you could use a single template template argument to specify the Iterator type and only need to write it once).

---

Step 2: There's a standard algorithm for that already. You don't need to write that loop.

---

(value >> (index * 8)) & 0xFF is written more than once. How the key byte is extracted should be abstracted. I'm surprised to see it written this way, as opposed to viewing the value as an array of std::byte. This only works for value types that are integers.

---

Generally, a function that has "steps" should actually be separate functions.

---

You have one test case? You can generate random collections of different sizes and test the result of your function call with is_sorted, or a call to the standard library sort. With the latter you also have the opportunity to compare the speeds. If you test different container types as well, you might find that your algorithm is faster when you don't have efficient random-access iterators for the collection being sorted. But std::list is only forward iterating and you need bidirectional iterators.

With your one single test case, you don't need to make it a vector but could use a plain array.