代码

#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];
    for(auto it=begin;it<end;it++)
    {
        Ty n = *it;
        prefix[0][n%RADIX]++;
        prefix[1][(n>>11)%RADIX]++;
        prefix[2][n>>22]++;
    }
    for(int j=0;j<segments;j++)
    {
        Ty pre=0,last=prefix[j][0];
        prefix[j][0]=0;
        for(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);
    }
    if(it_dst==&begin[0])
    {
        std::copy(tmp,tmp+len,begin);
    }
    delete[] tmp;
}

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

评测结果