基数ソート

概要

数を $k$ 進数表記したときの下1桁目でソート -> 下2桁目でソート -> … と繰り返す．下の実装は signed/unsigned 整数だけ対応．

オブジェクトを単なるビット列としてみれば任意の型に対応できるが，float には NaN があったりだとか，std::pair は first, second の順に配置されているのに std::tuple は n-1, … , 0 と逆順だったりとか罠が多いので一般化は諦めた．

計算量

$O(kn)$．ただし $k$ は桁数であり，この実装では $2^{16}$ なので char だと $k=1$, int だと $k=2$, long long だと $k=4$ のようになる． std::sort と比べると，乱数列に対して速いがソート済みの列に対しては遅い．

実装

template <typename T>
void radix_sort(T *l, T *r) {
    std::size_t n = r - l;
    if (n <= 1) return;
    constexpr std::size_t W = 16;
    constexpr unsigned M = (1 << W) - 1;
    constexpr std::size_t L = (8 * sizeof(T) + W - 1) / W;
    auto x = l, temp = new T[n];
    auto acc = new int[M + 2]();
    for (std::size_t i = 0; i < L; ++i) {
        if (i) memset(acc, 0, sizeof(int) * (M + 2));
        for (std::size_t j = 0; j < n; ++j) acc[1 + (x[j] >> (W * i) & M)]++;
        for (std::size_t j = 0; j < M + 1; ++j) acc[j + 1] += acc[j];
        for (std::size_t j = 0; j < n; ++j) temp[acc[x[j] >> (W * i) & M]++] = x[j];
        for (std::size_t j = 0; j < n; ++j) std::swap(temp[j], x[j]);
    }
    if (std::is_signed<T>()) {
        std::rotate(x, std::find_if(x, x + n, [](T x) { return x < 0; }), x + n);
    }
    delete[] acc;
    delete[] temp;
}

検証

AOJ10029 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2439444