代码

#include <algorithm>
#include <cstdint>

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;
    constexpr Ty RADIX_2 = RADIX/2;
    LenTy len = end - begin;
    end = begin + len;
    LenTy  prefix[segments][RADIX]={};
    auto tmp = new Ty[len];
    for(auto it=begin,it1 = reinterpret_cast<uint64_t*>(tmp);it<end;it+=2,it1++)
    {
        uint64_t n = *reinterpret_cast<uint64_t*>(it);
        *it1 = n;
        prefix[0][n%RADIX]++;
        prefix[1][(n>>11)%RADIX]++;
        prefix[2][(n>>22)%RADIX_2]++;
        prefix[0][(n>>32)%RADIX]++;
        prefix[1][(n>>43)%RADIX]++;
        prefix[2][n>>54]++;
    }
    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=&tmp[0],it_dst=&begin[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)
        {
            /*
            Ty org = *it;
            LenTy rem = (org>>shift)%RADIX;
            LenTy indx=prefix[seg][rem];
            it_dst[indx] = org;
            prefix[seg][rem]=indx+1;*/
            uint64_t org = *reinterpret_cast<uint64_t*>(it);
            Ty hi = org>>32;
            org &= UINT32_MAX;
            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);
    }
    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);
}

评测结果