代码

// 1001a: sort n=10000. 4-pass LSD byte radix, u16 counters, unroll 4/8. WS: 54.8us/sort
typedef unsigned u32;
static unsigned short h[4][256];
void sort(unsigned *a, int n) {
    static u32 tmp[1<<16];
    for (int i=0;i<256;i++){h[0][i]=0;h[1][i]=0;h[2][i]=0;h[3][i]=0;}
    int i=0;
    for (; i+7<n; i+=8){
        u32 v0=a[i],v1=a[i+1],v2=a[i+2],v3=a[i+3],v4=a[i+4],v5=a[i+5],v6=a[i+6],v7=a[i+7];
        h[0][v0&255]++; h[1][(v0>>8)&255]++; h[2][(v0>>16)&255]++; h[3][v0>>24]++;
        h[0][v1&255]++; h[1][(v1>>8)&255]++; h[2][(v1>>16)&255]++; h[3][v1>>24]++;
        h[0][v2&255]++; h[1][(v2>>8)&255]++; h[2][(v2>>16)&255]++; h[3][v2>>24]++;
        h[0][v3&255]++; h[1][(v3>>8)&255]++; h[2][(v3>>16)&255]++; h[3][v3>>24]++;
        h[0][v4&255]++; h[1][(v4>>8)&255]++; h[2][(v4>>16)&255]++; h[3][v4>>24]++;
        h[0][v5&255]++; h[1][(v5>>8)&255]++; h[2][(v5>>16)&255]++; h[3][v5>>24]++;
        h[0][v6&255]++; h[1][(v6>>8)&255]++; h[2][(v6>>16)&255]++; h[3][v6>>24]++;
        h[0][v7&255]++; h[1][(v7>>8)&255]++; h[2][(v7>>16)&255]++; h[3][v7>>24]++;
    }
    for (; i<n; i++){u32 v=a[i]; h[0][v&255]++; h[1][(v>>8)&255]++; h[2][(v>>16)&255]++; h[3][v>>24]++;}
    for (int p=0;p<4;p++){
        unsigned s=0; for(int k=0;k<256;k++){unsigned c=h[p][k]; h[p][k]=(unsigned short)s; s+=c;}
        u32 *src=(p&1)?tmp:a, *dst=(p&1)?a:tmp; int sh=p*8; i=0;
        if(p==3){ for(;i<n;i++){u32 v=src[i]; dst[h[3][v>>24]++]=v;} }
        else for(;i+3<n;i+=4){ u32 v0=src[i],v1=src[i+1],v2=src[i+2],v3=src[i+3];
            dst[h[p][(v0>>sh)&255]++]=v0; dst[h[p][(v1>>sh)&255]++]=v1;
            dst[h[p][(v2>>sh)&255]++]=v2; dst[h[p][(v3>>sh)&255]++]=v3; }
        for(;i<n;i++){u32 v=src[i]; dst[h[p][(v>>sh)&255]++]=v;}
    }
}

评测结果