代码

// Duck.ac 1001, C++17 / AVX2. Entry: void sort(unsigned*, int).
// 84 packed 24-bit values per 256-byte block; exact recovery on overflow.
// 25,344-byte guards protect top buckets between 8,192-input checks.
// n <= 100,000,000; input and all workspaces fit within 800 MiB.
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <immintrin.h>
#include <array>

#pragma GCC optimize("O3,unroll-loops,no-strict-aliasing")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

#include <cstdlib>

namespace v2_tail {
inline unsigned load16(const uint16_t* p) {
    uint16_t v;std::memcpy(&v,p,2);return v;
}
[[gnu::noinline]] inline void dense(const uint16_t* src,unsigned n,unsigned* dst,unsigned base) {
    alignas(64) unsigned counts[65536]={};
    for(unsigned i=0;i<n;++i)++counts[load16(src+i)];
    for(unsigned v=0;v<65536;++v)
        for(unsigned c=counts[v];c;--c)*dst++=base|v;
}
template<int J> inline __m256i merge_step(__m256i x) {
    alignas(32) static constexpr auto perm=[] {
        std::array<uint8_t,32>a{};
        for(unsigned i=0;i<32;++i)a[i]=uint8_t((i&15)^J);
        return a;
    }();
    __m256i y=_mm256_shuffle_epi8(x,_mm256_load_si256((const __m256i*)perm.data()));
    __m256i lo=_mm256_min_epu8(x,y),hi=_mm256_max_epu8(x,y);
    if constexpr(J>1)return _mm256_blend_epi16(lo,hi,J==4?0xcc:0xaa);
    else return _mm256_blendv_epi8(lo,hi,_mm256_set1_epi16(short(0xff00)));
}
inline void write8(__m128i x,unsigned* dst,unsigned c,unsigned base,unsigned* end) {
    __m256i y=_mm256_or_si256(_mm256_cvtepu8_epi32(x),_mm256_set1_epi32(base));
    if(end-dst>=8)_mm256_storeu_si256((__m256i*)dst,y);
    else _mm256_maskstore_epi32((int*)dst,_mm256_cmpgt_epi32(_mm256_set1_epi32(c),
                                      _mm256_setr_epi32(0,1,2,3,4,5,6,7)),y);
}

inline void column_sort8(const uint8_t* src,uint8_t* out) {
    __m256i x[8],a[8],b[8];
    #pragma GCC unroll 8
    for(unsigned i=0;i<8;++i)x[i]=_mm256_load_si256((const __m256i*)(src+256*i));
    #define V2_C(A,B) do {__m256i lo=_mm256_min_epu8(x[A],x[B]);x[B]=_mm256_max_epu8(x[A],x[B]);x[A]=lo;} while(0)
    V2_C(0,2);V2_C(1,3);V2_C(4,6);V2_C(5,7);
    V2_C(0,4);V2_C(1,5);V2_C(2,6);V2_C(3,7);
    V2_C(0,1);V2_C(2,3);V2_C(4,5);V2_C(6,7);
    V2_C(2,4);V2_C(3,5);V2_C(1,4);V2_C(3,6);
    V2_C(1,2);V2_C(3,4);V2_C(5,6);
    #undef V2_C
    #pragma GCC unroll 4
    for(unsigned i=0;i<4;++i) {
        a[2*i]=_mm256_unpacklo_epi8(x[2*i],x[2*i+1]);
        a[2*i+1]=_mm256_unpackhi_epi8(x[2*i],x[2*i+1]);
    }
    #pragma GCC unroll 2
    for(unsigned i=0;i<2;++i) {
        #pragma GCC unroll 2
        for(unsigned j=0;j<2;++j) {
            b[4*i+2*j]=_mm256_unpacklo_epi16(a[4*i+j],a[4*i+j+2]);
            b[4*i+2*j+1]=_mm256_unpackhi_epi16(a[4*i+j],a[4*i+j+2]);
        }
    }
    #pragma GCC unroll 4
    for(unsigned i=0;i<4;++i) {
        __m256i lo=_mm256_unpacklo_epi32(b[i],b[i+4]),hi=_mm256_unpackhi_epi32(b[i],b[i+4]);
        _mm_store_si128((__m128i*)(out+32*i),_mm256_castsi256_si128(lo));
        _mm_store_si128((__m128i*)(out+32*i+16),_mm256_castsi256_si128(hi));
        _mm_store_si128((__m128i*)(out+128+32*i),_mm256_extracti128_si256(lo,1));
        _mm_store_si128((__m128i*)(out+128+32*i+16),_mm256_extracti128_si256(hi,1));
    }
}
inline __m128i merge_sorted8(const uint8_t* a,const uint8_t* b) {
    __m128i high=_mm_shuffle_epi8(_mm_loadl_epi64((const __m128i*)b),
                                  _mm_setr_epi8(7,6,5,4,3,2,1,0,15,14,13,12,11,10,9,8));
    __m128i low=_mm_loadl_epi64((const __m128i*)a);
    __m256i x=_mm256_castsi128_si256(_mm_unpacklo_epi64(_mm_min_epu8(low,high),_mm_max_epu8(low,high)));
    return _mm256_castsi256_si128(merge_step<1>(merge_step<2>(merge_step<4>(x))));
}

inline void columns_merge(const uint16_t* src,unsigned n,unsigned* dst,unsigned base,unsigned* end) {
    if(n<64) {
        unsigned copy[64];for(unsigned i=0;i<n;++i)copy[i]=base|load16(src+i);
        std::sort(copy,copy+n);std::memcpy(dst,copy,n*4);return;
    }
    if(n>8192) {dense(src,n,dst,base);return;}
    alignas(64) static uint8_t columns[256*8192];
    alignas(64) unsigned count[256];
    std::memset(columns,255,4096);
    for(unsigned i=0;i<256;++i)count[i]=i;
    for(unsigned i=0;i<n;++i) {
        unsigned v=load16(src+i),h=v>>8,at=count[h];
        count[h]=at+256;columns[at]=uint8_t(v);
    }
    unsigned over=0;
    for(unsigned i=0;i<256;++i) {count[i]>>=8;over|=count[i]>32;}
    if(over) {dense(src,n,dst,base);return;}
    for(unsigned block=0;block<256;block+=32) {
        alignas(32) uint8_t first[256],second[256];
        column_sort8(columns+block,first);column_sort8(columns+2048+block,second);
        for(unsigned i=0;i<32;++i) {
            unsigned h=block+i,c=count[h],p=base|(h<<8);
            if(c<=8) {if(c)write8(_mm_loadl_epi64((const __m128i*)(first+8*i)),dst,c,p,end);}
            else if(c<=16) {
                __m128i x=merge_sorted8(first+8*i,second+8*i);
                write8(x,dst,8,p,end);write8(_mm_srli_si128(x,8),dst+8,c-8,p,end);
            } else {
                uint8_t copy[32];for(unsigned j=0;j<c;++j)copy[j]=columns[256*j+h];
                std::sort(copy,copy+c);for(unsigned j=0;j<c;++j)dst[j]=p|copy[j];
            }
            dst+=c;
        }
    }
}
} // namespace v2_tail

namespace fastsort {
using U=unsigned; using B=unsigned char; using H=uint16_t; using Z=uint64_t;
static B* mem;
inline U get(const B* p){U x;std::memcpy(&x,p,4);return x&0xffffff;}
inline U at(const B* p,U i){return get(p+size_t(i/84)*256+i%84*3);}
inline bool fits(B**p,B**e){
    __m256i bad=_mm256_setzero_si256();
    for(int k=0;k<256;k+=4)bad=_mm256_or_si256(bad,_mm256_cmpgt_epi64(
        _mm256_load_si256((__m256i*)(p+k)),_mm256_load_si256((__m256i*)(e+k))));
    return _mm256_testz_si256(bad,bad);
}
bool split(U*a,U n,U*cap,B**start,U*cnt){
    alignas(64) B cache[65536]={};
    alignas(64) B *p[256],*e[256];
    U pos[256];size_t off=0;
    for(U k=0;k<256;++k){
        start[k]=p[k]=mem+off;e[k]=p[k]+((size_t(cap[k])+83)/84)*256;
        off=size_t(e[k]-mem)+25344;pos[k]=k*256;
    }
    for(U i=0;i<n;){
        U stop=std::min(n,i+8192);
        #pragma GCC unroll 4
        for(;i<stop;++i){
            U x=a[i],k=x>>24,t=pos[k];std::memcpy(cache+t,&x,4);t+=3;
            if(__builtin_expect((t&255)==252,0)){
                t-=252;
                _mm256_stream_si256((__m256i*)(p[k]+0),_mm256_load_si256((__m256i*)(cache+t+0)));
                _mm256_stream_si256((__m256i*)(p[k]+32),_mm256_load_si256((__m256i*)(cache+t+32)));
                _mm256_stream_si256((__m256i*)(p[k]+64),_mm256_load_si256((__m256i*)(cache+t+64)));
                _mm256_stream_si256((__m256i*)(p[k]+96),_mm256_load_si256((__m256i*)(cache+t+96)));
                _mm256_stream_si256((__m256i*)(p[k]+128),_mm256_load_si256((__m256i*)(cache+t+128)));
                _mm256_stream_si256((__m256i*)(p[k]+160),_mm256_load_si256((__m256i*)(cache+t+160)));
                _mm256_stream_si256((__m256i*)(p[k]+192),_mm256_load_si256((__m256i*)(cache+t+192)));
                _mm256_stream_si256((__m256i*)(p[k]+224),_mm256_load_si256((__m256i*)(cache+t+224)));
                p[k]+=256;
            }pos[k]=t;
        }
        if(!fits(p,e)){_mm_sfence();return false;}
    }
    for(U k=0;k<256;++k){
        U r=pos[k]&255;cnt[k]=U((p[k]-start[k])/256)*84+r/3;
        if(r){std::memcpy(p[k],cache+k*256,256);p[k]+=256;}
    }
    _mm_sfence();return fits(p,e);
}
void leaf(const B*s,U n,U base,U*d){v2_tail::columns_merge((const H*)s,n,d,base,d+n);}
void middle(const B*s,U n,U base,U*d){
    if(n<4096){for(U i=0;i<n;++i)d[i]=base|at(s,i);std::sort(d,d+n);return;}
    U cnt[256]={},begin[257],pos[256];
    if(n>600000||n<16384){
        for(U i=0;i<n;++i)++cnt[at(s,i)>>16];
        begin[0]=0;
        for(U k=0;k<256;++k){pos[k]=begin[k];begin[k+1]=begin[k]+cnt[k];}
        for(U i=0;i<n;++i){U x=at(s,i);H lo=x;std::memcpy((B*)d+2*pos[x>>16]++,&lo,2);}
        for(int k=255;k>=0;--k)if(cnt[k])leaf((B*)d+2*begin[k],cnt[k],base|(U(k)<<16),d+begin[k]);
        return;
    }
    B*tmp=mem+380000000;B*p[256];
    U bytes=0;
    for(U k=0;k<256;++k){begin[k]=bytes;p[k]=tmp+bytes;bytes+=2*((n+127)/128);}
    begin[256]=bytes;
    for(;;){
        U i=0;const B*b=s;
        for(;i+84<=n;i+=84,b+=256){
            _mm_prefetch((const char*)((uintptr_t)b+256),_MM_HINT_T0);
            #pragma GCC unroll 14
            for(U j=0;j<84;++j){U x=get(b+j*3);H lo=x;std::memcpy(p[x>>16],&lo,2);p[x>>16]+=2;}
        }
        for(;i<n;++i){U x=at(s,i);H lo=x;std::memcpy(p[x>>16],&lo,2);p[x>>16]+=2;}
        bool bad=false;
        for(U k=0;k<256;++k){cnt[k]=U(p[k]-(tmp+begin[k]))/2;bad|=p[k]>tmp+begin[k+1];}
        if(!bad)break;
        bytes=0;
        for(U k=0;k<256;++k){begin[k]=bytes;p[k]=tmp+bytes;bytes+=2*cnt[k];}
        begin[256]=bytes;
    }
    for(U k=0;k<256;++k){if(cnt[k])leaf(tmp+begin[k],cnt[k],base|(k<<16),d);d+=cnt[k];}
}
}
void sort(unsigned*a,int n){
    using namespace fastsort;
    if(n<2)return;
    if(n<4096||n>100000000){std::sort(a,a+n);return;}
    void*raw=std::malloc(384000063); if(!raw){std::sort(a,a+n);return;}
    mem=(B*)((uintptr_t(raw)+63)&~uintptr_t(63));
    U cap[256],cnt[256];B*start[256];
    for(U k=0;k<256;++k)cap[k]=U((Z(n)+255)/256)*6/5+32;
    if(!split(a,n,cap,start,cnt)){
        std::memset(cap,0,sizeof cap);for(int i=0;i<n;++i)++cap[a[i]>>24];
        split(a,n,cap,start,cnt);
    }
    U off=0;for(U k=0;k<256;++k){if(cnt[k])middle(start[k],cnt[k],k<<24,a+off);off+=cnt[k];}
    std::free(raw);
}

评测结果