代码

// Duck.ac 1001 | C++17 / AVX2 | void sort(unsigned*, int)
// Paired cursors + packed24 radix + AVX2 byte sorting networks.
// Pairing idea: Arman/Loguinov, F5 (ICDE 2026), Algorithm 4.
#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 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)__asm__ volatile("vmovdqu {%1, %0|%0, %1}" : "=m"(*reinterpret_cast<__m256i_u*>(dst)) : "x"(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 CE(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)
    CE(0,2);CE(1,3);CE(4,6);CE(5,7);
    CE(0,4);CE(1,5);CE(2,6);CE(3,7);
    CE(0,1);CE(2,3);CE(4,5);CE(6,7);
    CE(2,4);CE(3,5);CE(1,4);CE(3,6);
    CE(1,2);CE(3,4);CE(5,6);
    #undef CE
    #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;
    unsigned i=0;
    for(;i+2<=n;i+=2) {
        unsigned v0=load16(src+i),v1=load16(src+i+1),h0=v0>>8,h1=v1>>8;
        unsigned a0=count[h0],a1=count[h1];
        if(h0==h1)a1+=256;
        count[h0]=a0+256;count[h1]=a1+256;
        columns[a0]=uint8_t(v0);columns[a1]=uint8_t(v1);
    }
    for(;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 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/85)*256+i%85*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);
}
[[gnu::always_inline]] inline U put(U x,U k,U t,B* cache,B**p) {
    std::memcpy(cache+t,&x,4);t+=3;
    if(__builtin_expect((t&255)==255,0)) {
        t-=255;
        #pragma GCC unroll 8
        for(U j=0;j<256;j+=32)_mm256_stream_si256((__m256i*)(p[k]+j),
            _mm256_load_si256((const __m256i*)(cache+t+j)));
        p[k]+=256;
    }
    return t;
}
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])+84)/85)*256;
        off=size_t(e[k]-mem)+25088;pos[k]=k*256;
    }
    for(U i=0;i<n;) {
        U stop=std::min(n,i+8192);
        #pragma GCC unroll 2
        for(;i+1<stop;i+=2) {
            U x0=a[i],x1=a[i+1],k0=x0>>24,k1=x1>>24;
            U t0=pos[k0],t1=pos[k1];
            t0=put(x0,k0,t0,cache,p);pos[k0]=t0;
            asm("cmpl %3,%2; cmovel %1,%0":"+r"(t1):"r"(t0),"r"(k1),"r"(k0):"cc");
            t1=put(x1,k1,t1,cache,p);pos[k1]=t1;
        }
        if(i<stop){U x=a[i++],k=x>>24;pos[k]=put(x,k,pos[k],cache,p);}
        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)*85+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){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+85<=n;i+=85,b+=256){
            _mm_prefetch((const char*)((uintptr_t)b+256),_MM_HINT_T0);
            #pragma GCC unroll 17
            for(U j=0;j<85;++j){H lo;std::memcpy(&lo,b+j*3,2);U k=b[j*3+2];std::memcpy(p[k],&lo,2);p[k]+=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);
}

评测结果