This started out with my answer to Radix Sort on an Array of Strings?. Since I intend to write a generic radix sort for my own purposes anyway, I continued a little bit, and here is a version tested on:

  1. a fixed std::array of unsigned numbers, each treated as a fixed sequence of bytes from least-significant (right) to most-significant (left), to be sorted by natural order; and

  2. an std::vector of std::strings, each treated as a variable-length sequence of characters from left to right, to be sorted by lexicographical order.

I will eventually make this more and more generic, but I am posting it here before it becomes extremely abstract. For now, it is not even parametrized with respect to ascending/descending order, but most interesting generalizations will be towards

  • all scalar types: signed integers, floating-point, enums, pointers, etc.;
  • sequences (built-in arrays or standard containers) of previous types to be sorted lexicographically;
  • tuples or structures of previous types to be sorted lexicographically;
  • recursive application of the above.

Here it is (live example):

#include <type_traits>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <iostream>

template<bool B>
using expr = std::integral_constant<bool, B>;


template <typename View, bool Var, bool Flip, size_t Radix>
class radix_sort
    template <typename I, typename S>
    void sort(I& idx, const S& slice) const
        using A = std::array<size_t, (Var ? Radix + 1 : Radix)>;

        A count = {};
        I prev = idx;

        for (auto i : prev)

        A offset = {{0}};
        std::partial_sum(count.begin(), count.end() - 1, offset.begin() + 1);

        for (auto i : prev)
            idx[offset[slice(i)]++] = i;

    template <typename D>
    std::vector<size_t> operator()(const D& data) const
        std::vector<size_t> idx(data.size());
        std::iota(idx.begin(), idx.end(), 0);

        if (data.size() < 2)
            return idx;

        View view;
        using R = decltype(data[0]);

        size_t width = Var ?
            view.size(*std::max_element(data.begin(), data.end(),
                [view](R a, R b) { return view.size(a) < view.size(b); }
            )) :

        for (size_t d = 0; d < width; ++d)
            size_t digit = Flip ? width - d - 1 : d;
            sort(idx, [&view, &data, digit] (size_t i) {
                return size_t(view.at(expr<Var>(), data[i], digit));

        return idx;


struct int_view
    template<typename A>
    size_t size(const A& a) const { return sizeof(a); }

    template <bool B, typename E>
    unsigned char at(expr<B>, const E& elem, size_t pos) const
        return (elem >> pos) & 0xFF;


struct array_view
    template<typename A>
    size_t size(const A& a) const { return a.size(); }

    template <typename E>
    typename E::value_type
    at(std::false_type, const E& elem, size_t pos) const
        return elem[pos];

    template <typename E>
    typename E::value_type
    at(std::true_type, const E& elem, size_t pos) const
        using T = typename E::value_type;
        return pos < elem.size() ? elem[pos] + T(1) : T(0);


std::array<unsigned, 100>
    return {{
        162, 794, 311, 528, 165, 601, 262, 654, 689, 748,
        450,  83, 228, 913, 152, 825, 538, 996,  78, 442,
        106, 961,   4, 774, 817, 868,  84, 399, 259, 800,
        431, 910, 181, 263, 145, 136, 869, 579, 549, 144,
        853, 622, 350, 513, 401,  75, 239, 123, 183, 239,
        417,  49, 902, 944, 490, 489, 337, 900, 369, 111,
        780, 389, 241, 403,  96, 131, 942, 956, 575,  59,
        234, 353, 821,  15,  43, 168, 649, 731, 647, 450,
        547, 296, 744, 188, 686, 183, 368, 625, 780,  81,
        929, 775, 486, 435, 446, 306, 508, 510, 817, 794

    return {
        "main street",
        "impaled decolonizing",
        "axial satisfactoriness",
        "creams surges",
        "zouaves dishpan",
        "powerless tiding",


template<typename G, typename S>
void test(G generate, S sort)
    auto data = generate();
    auto idx = sort(data);

    std::cout << "sorted data:" << std::endl;
    for (auto i : idx)
        std::cout << data[i] << std::endl;
    std::cout << std::endl;

int main()
    test(numbers, radix_sort<int_view,   false, false, 256>());
    test(strings, radix_sort<array_view, true,  true,  128>());

I would appreciate the following:

  1. General comments on both algorithm and style.
  2. Any more specific comments on correctness and efficiency.
  3. Is the code self-evident, so that no comments are practically needed? For instance, is it evident what "views" and "slices" are?
  4. I think I'll find my way with signed integral and remaining types, but is there a clean, standard, portable way of obtaining integral representations of mantissa + exponent of floating-point numbers, or should one resort to type casts and bitwise operations according to IEEE standard representations?

EDIT Please note I made a slight simplification in radix_sort::sort() compared to my original post.


1 Answer 1



You should reorder your headers in alphabetic order. It will help when you will have to check whether a header is already included or not:

#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <type_traits>
#include <vector>

You have many type names that are a single capital letter, which quite hinder readability. For example, you could change A into Arr. For many of them, I can't guess which "concept" should satisfy template parameter types. Apart from T and U for any type or N for any integral value, it is pretty uncommon to use a single capital letter.

You should also be consistent when naming your types: do you want them to be capitalized or not? If you want to be consistent, you could for example rename expr into Expr.

Generally speaking, the style is quite good: the indentation is clear, the lines are not too long and you don't seem to have any magic number besides 0xFF. I wish I could always read code that clean.


In radix_sort::sort, you use member functions begin and end. It is now considered good style to write std::begin and std::end wherever possible so that you won't get into trouble if the code is changed. Moreover, in C++14, you will have std::cbegin and std::cend that rely on member begin and end. That means that pre-C++11 containers that do not provide member cbegin and cend can also be used.

  • 1
    \$\begingroup\$ Thanks! About capital letters: in general I use lowercase for both types and objects; and uppercase only for template parameters and single-letter private type aliases. Some template parameters are small words (like View, Radix) but others are single-letter when context helps (e.g. A = std::array, S& slice, or G generate). I guess single-letter is what I should be more careful about. For instance, R = decltype(data[0])` is apparently a (const) reference to some type to me, but maybe not to others. In which case ref might be better, right? \$\endgroup\$
    – iavr
    Apr 14, 2014 at 9:50
  • \$\begingroup\$ @iavr Definetely, I had no idea what R was for actually. It's good that your public interface is clean, but it's even better if other people can understand and maintain your code :) \$\endgroup\$
    – Morwenn
    Apr 14, 2014 at 9:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.