代码

#include <algorithm>
#include <cstdint>

template<typename Iter>
void radix_sort_u32(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=8;
    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+=2)
    {
        uint64_t n = *reinterpret_cast<uint64_t*>(&it[0]);
        prefix[0][(n)%RADIX]++;
        prefix[1][(n>>RADIX_LEN)%RADIX]++;
        prefix[2][(n>>RADIX_LEN*2)%RADIX]++;
        prefix[3][(n>>RADIX_LEN*3)%RADIX]++;
        prefix[0][(n>>RADIX_LEN*4)%RADIX]++;
        prefix[1][(n>>RADIX_LEN*5)%RADIX]++;
        prefix[2][(n>>RADIX_LEN*6)%RADIX]++;
        prefix[3][(n>>RADIX_LEN*7)%RADIX]++;
    }
    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+=2)
        {
            uint64_t org = *reinterpret_cast<uint64_t*>(&it[0]);
            Ty hi = org>>32;
            LenTy rem = (org>>shift)%RADIX;
            LenTy indx=prefix[seg][rem];
            it_dst[indx] = org;
            prefix[seg][rem] = indx+1;
            rem = (hi>>shift)%RADIX;
            indx=prefix[seg][rem];
            it_dst[indx] = hi;
            prefix[seg][rem] = indx+1;
        }
        std::swap(it_org,it_dst);
    }
    delete[] tmp;
}
void sort(unsigned *a, int n) {
	radix_sort_u32(a,a+n);
}

评测结果