代码

// 1001c: sort n = 1<<27 unsigned. Fused-histogram 4-pass LSD byte radix.
typedef unsigned u32;
static u32 tmpbuf[1 << 27];
static u32 h0[256], h1[256], h2[256], h3[256];
void sort(u32 *a, int n) {
    u32 *tmp = tmpbuf;
    for (int i=0;i<256;i++){h0[i]=0;h1[i]=0;h2[i]=0;h3[i]=0;}
    int i=0;
    for (; i+3<n; i+=4) {
        u32 v0=a[i],v1=a[i+1],v2=a[i+2],v3=a[i+3];
        h0[v0&255]++; h0[v1&255]++; h0[v2&255]++; h0[v3&255]++;
    }
    for (; i<n; i++) h0[a[i]&255]++;
    u32 s=0; for(i=0;i<256;i++){u32 c=h0[i];h0[i]=s;s+=c;}
    for (i=0;i+3<n;i+=4){ u32 v0=a[i],v1=a[i+1],v2=a[i+2],v3=a[i+3];
        tmp[h0[v0&255]++]=v0; tmp[h0[v1&255]++]=v1; tmp[h0[v2&255]++]=v2; tmp[h0[v3&255]++]=v3;
        h1[(v0>>8)&255]++; h1[(v1>>8)&255]++; h1[(v2>>8)&255]++; h1[(v3>>8)&255]++; }
    for (;i<n;i++){u32 v=a[i]; tmp[h0[v&255]++]=v; h1[(v>>8)&255]++;}
    s=0; for(i=0;i<256;i++){u32 c=h1[i];h1[i]=s;s+=c;}
    for (i=0;i+3<n;i+=4){ u32 v0=tmp[i],v1=tmp[i+1],v2=tmp[i+2],v3=tmp[i+3];
        a[h1[(v0>>8)&255]++]=v0; a[h1[(v1>>8)&255]++]=v1; a[h1[(v2>>8)&255]++]=v2; a[h1[(v3>>8)&255]++]=v3;
        h2[(v0>>16)&255]++; h2[(v1>>16)&255]++; h2[(v2>>16)&255]++; h2[(v3>>16)&255]++; }
    for (;i<n;i++){u32 v=tmp[i]; a[h1[(v>>8)&255]++]=v; h2[(v>>16)&255]++;}
    s=0; for(i=0;i<256;i++){u32 c=h2[i];h2[i]=s;s+=c;}
    for (i=0;i+3<n;i+=4){ u32 v0=a[i],v1=a[i+1],v2=a[i+2],v3=a[i+3];
        tmp[h2[(v0>>16)&255]++]=v0; tmp[h2[(v1>>16)&255]++]=v1; tmp[h2[(v2>>16)&255]++]=v2; tmp[h2[(v3>>16)&255]++]=v3;
        h3[v0>>24]++; h3[v1>>24]++; h3[v2>>24]++; h3[v3>>24]++; }
    for (;i<n;i++){u32 v=a[i]; tmp[h2[(v>>16)&255]++]=v; h3[v>>24]++;}
    s=0; for(i=0;i<256;i++){u32 c=h3[i];h3[i]=s;s+=c;}
    for (i=0;i+3<n;i+=4){ u32 v0=tmp[i],v1=tmp[i+1],v2=tmp[i+2],v3=tmp[i+3];
        a[h3[v0>>24]++]=v0; a[h3[v1>>24]++]=v1; a[h3[v2>>24]++]=v2; a[h3[v3>>24]++]=v3; }
    for (;i<n;i++){u32 v=tmp[i]; a[h3[v>>24]++]=v;}
}

评测结果