代码

#include<cstring>
#include<algorithm>
namespace my_sort{
    #define FORCE_COL static_assert(true,"")
    using 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
}
auto &sort=my_sort::sort;

评测结果