代码

#include<cstring>
#include<algorithm>
#define FORCE_COL static_assert(true,"")
#define uint unsigned
void radix_sort(uint *arr,uint *aux,int n){
    static uint mask=(1<<16)-1;
    static uint cnt[1<<16];
    static int i;
    #define work()                        \
    memset(cnt,0,sizeof(cnt));            \
    for(i=0;i^n;++i)++cnt[fn(arr[i])];    \
    for(i=0;i^mask;++i)cnt[i+1]+=cnt[i];  \
    for(i=n-1;i>=0;--i){                  \
        aux[--cnt[fn(arr[i])]]=arr[i];    \
    }                                     \
    memmove(arr,aux,sizeof(uint)*n);      \
    FORCE_COL
    #define fn(x) (((x)<<16)>>16)
    work();
    #undef fn
    #define fn(x) ((x)>>16)
    work();
    #undef fn
    #undef work
}
void sort(uint *a, int n) {
    static uint b[50000000];
    static int ln,rn;
    ln=n>>1,rn=n-ln;
    radix_sort(a,b,ln);
    radix_sort(a+ln,b,rn);
    memmove(b,a,sizeof(uint)*ln);
    std::merge(a+ln,a+n,b,b+ln,a);
}
#undef FORCE_COL
#undef uint

评测结果