Корень Сортировка по массиву строк?

Очень похоже на iavr, но сортировка на месте (сравнена с решением iavr с g ++ -O3 и занимает около 2020 мс по сравнению с 1780 мс iavr), наслаждаясь обычный интерфейс и многократный код. Проблема с реализацией Iavr заключается в том, что его логика работает только с контейнерами строк и не может быть легко расширяема для других типов. Очевидно, что его специализированная версия более эффективна, но, возможно, стоило бы пожертвовать некоторой производительностью ради регулярности.
Вы можете найти остальную часть кода на реализация сортировки по основанию

General Radix сортировать:

template <typename T>
using Iter_value = std::iterator_traits<T>::value_type;

// intermediate struct to get partial template specialization
template<typename Iter, typename T, size_t range = 256>
struct rdx_impl {
static void rdx_sort(Iter begin, Iter end, int bits) {
// bits is # bits to consider up to if a max val is known ahead of time
// most efficent (theoretically) when digits are base n, having lg(n) bits
constexpr size_t digit_bits {8};        // # bits in digit, 8 works well for 32 and 64 bit vals

size_t d {0};                   // current digit #
for (long long mask = (1 << digit_bits) - 1;
d * digit_bits < bits;) {// ex. 0x000000ff for setting lower 8 bits on 32 bit num
cnt_sort(begin, end, range, Digit_cmp<T>(mask, digit_bits*d));
++d;
}
}
};

// specialization of rdx_sort for strings
struct Shorter {
template <typename Seq>
bool operator()(const Seq& a, const Seq& b) { return a.size() < b.size(); }
};
template <typename Iter>
struct rdx_impl<Iter, std::string> {    // enough to hold ASCII char range
static void rdx_sort(Iter begin, Iter end, int) {
// ignore additional int argument
int len_max = std::max_element(begin, end, Shorter())->size();
for (int d = len_max - 1; d >= 0; --d)
cnt_sort(begin, end, 128, Digit_cmp<std::string>(d));
}
};

// generic call interface for all iterators
template <typename Iter>   // use intermediate struct for partial specialization
void rdx_sort(Iter begin, Iter end, int bits) {
rdx_impl<Iter, Iter_value<Iter>>::rdx_sort(begin, end, bits);
}

Подсчет сортировки для сортировки по каждой цифре (по месту):

template <typename Iter, typename Op>
void cnt_sort(Iter begin, Iter end, size_t range, Op op) {
using T = typename Iter::value_type;
std::vector<int> counts(range);   // init to 0
for (auto i = begin; i != end; ++i) // count # elems == i
++counts[op(*i)];
for (size_t i = 1; i < range; ++i)
counts[i] += counts[i-1];   // turn into # elems <= i
std::vector<T> res(end - begin);
for (auto j = end;;) {
--j;
res[--counts[op(*j)]] = *j;
if (j == begin) break;
}
// ~18% of time is spent on copying
std::copy(res.begin(), res.end(), begin);
}

Извлечь значение цифры:

template <typename T>   // overload digit_cmp for non-integral types top provide radix sort with digits
class Digit_cmp {   // functor for comparing a "digit" (particular bits)
const long long mask; // 0..63 bitfield to test against
const size_t to_shift;
public:
Digit_cmp(long long m, size_t ts) : mask{m}, to_shift{ts} {}
// by default assumes integral, just shifts
size_t operator()(T n) const {    // char assuming r = 8
return (n >> to_shift) & mask; // shift then mask for unit digit
}
};
// specialization for strings
template <>
class Digit_cmp<std::string> {
const size_t digit;
public:
Digit_cmp(size_t d) : digit{d} {}
size_t operator()(const std::string& str) {
// 0 indicates past the end of the string
return str.size() > digit ? str[digit] : 0;
}
};