代码

typedef unsigned u32;
enum { RAD=2048, MASK=2047 };
static u32 temp[100000000], count[RAD], start[RAD], next[RAD];

static void inplace_pass(u32*a,int n,int shift){
    for(int i=0;i<RAD;++i)count[i]=0;
    for(int i=0;i<n;++i)++count[(a[i]>>shift)&MASK];
    u32 sum=0;
    for(int i=0;i<RAD;++i){start[i]=next[i]=sum;sum+=count[i];}
    for(int bucket=0;bucket<RAD;++bucket){
        u32 end=start[bucket]+count[bucket];
        while(next[bucket]<end){
            u32 p=next[bucket],v=a[p],b=(v>>shift)&MASK;
            if(b== (u32)bucket){++next[bucket];continue;}
            u32 q=next[b]++;a[p]=a[q];a[q]=v;
        }
    }
}

void sort(u32*a,int n){
    if(n<=100000000){
        u32*src=a,*dst=temp;
        for(int shift=0;shift<33;shift+=11){
            for(int i=0;i<RAD;++i)count[i]=0;
            for(int i=0;i<n;++i)++count[(src[i]>>shift)&MASK];
            u32 sum=0;for(int i=0;i<RAD;++i){u32 c=count[i];count[i]=sum;sum+=c;}
            for(int i=0;i<n;++i){u32 v=src[i];dst[count[(v>>shift)&MASK]++]=v;}
            u32*t=src;src=dst;dst=t;
        }
        if(src!=a)for(int i=0;i<n;++i)a[i]=src[i];
    }else{
        inplace_pass(a,n,0);inplace_pass(a,n,11);inplace_pass(a,n,22);
    }
}

评测结果