代码

#include<cstdint>
#include<algorithm>
template <typename Iter>
void radix_sort_u32x11(Iter begin, Iter end)
{
    using Ty = decltype(+begin[0]);
    using LenTy = uint32_t;
    //static_assert(std::is_same<Ty, uint32_t>::value, "Must be uint32 ary");
    constexpr int RADIX_LEN = 11;
    constexpr int segments = (sizeof(Ty) * 8 + RADIX_LEN - 1) / RADIX_LEN;
    constexpr Ty RADIX = Ty(1) << RADIX_LEN;
    LenTy len = end - begin;
    end = begin + len;
    LenTy prefix[segments][RADIX] = {};
    auto tmp = new Ty[len];
    // static Ty tmp[size_t(1e8)];
    for (auto it = begin; it < end; it++)
    {
        Ty n = *it;
        prefix[0][n % RADIX]++;
        prefix[1][(n >> RADIX_LEN) % RADIX]++;
        prefix[2][n >> RADIX_LEN * 2]++;
    }
    for (int j = 0; j < segments; j++)
    {
        Ty pre = 0, last = prefix[j][0];
        prefix[j][0] = 0;
        for (std::size_t i = 1; i < RADIX; i++)
        {
            pre = prefix[j][i];
            prefix[j][i] = prefix[j][i - 1] + last;
            last = pre;
        }
    }
    auto it_org = &begin[0], it_dst = &tmp[0];
    for (int seg = 0; seg < segments; seg++)
    {
        const int shift = seg * RADIX_LEN;
        auto org_end = it_org + len;
        for (auto it = it_org; it < org_end; it++)
        {
            Ty org = *it;
            LenTy rem = (org >> shift) % RADIX;
            LenTy indx = prefix[seg][rem];
            it_dst[indx] = org;
            prefix[seg][rem] = indx + 1;
        }
        std::swap(it_org, it_dst);
    }
    delete[] tmp;
}

void sort(unsigned *a, int n) {
    radix_sort_u32x11(a,a+n);
}

评测结果