代码

// 1001a: sort n=10000. 3-pass LSD radix with 11/11/10-bit digits: one fused
// histogram pass + 3 scatter passes (instead of 4), unrolled 8-wide.
typedef unsigned u32;
static unsigned short h0[2048], h1[2048], h2[1024];
void sort(unsigned *a, int n) {
    static u32 tmp[1 << 16];
    for (int i = 0; i < 2048; i++) { h0[i] = 0; h1[i] = 0; if (i < 1024) h2[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];
        h0[v0&2047]++; h1[(v0>>11)&2047]++; h2[v0>>22]++;
        h0[v1&2047]++; h1[(v1>>11)&2047]++; h2[v1>>22]++;
        h0[v2&2047]++; h1[(v2>>11)&2047]++; h2[v2>>22]++;
        h0[v3&2047]++; h1[(v3>>11)&2047]++; h2[v3>>22]++;
        h0[v4&2047]++; h1[(v4>>11)&2047]++; h2[v4>>22]++;
        h0[v5&2047]++; h1[(v5>>11)&2047]++; h2[v5>>22]++;
        h0[v6&2047]++; h1[(v6>>11)&2047]++; h2[v6>>22]++;
        h0[v7&2047]++; h1[(v7>>11)&2047]++; h2[v7>>22]++;
    }
    for (; i < n; i++) { u32 v=a[i]; h0[v&2047]++; h1[(v>>11)&2047]++; h2[v>>22]++; }
    unsigned s;
    s = 0; for (int k = 0; k < 2048; k++) { unsigned c = h0[k]; h0[k] = (unsigned short)s; s += c; }
    u32 *src = a, *dst = tmp;
    for (i = 0; i + 3 < n; i += 4) { u32 v0=src[i],v1=src[i+1],v2=src[i+2],v3=src[i+3];
        dst[h0[v0&2047]++]=v0; dst[h0[v1&2047]++]=v1; dst[h0[v2&2047]++]=v2; dst[h0[v3&2047]++]=v3; }
    for (; i < n; i++) { u32 v = src[i]; dst[h0[v&2047]++] = v; }
    src = tmp; dst = a;
    s = 0; for (int k = 0; k < 2048; k++) { unsigned c = h1[k]; h1[k] = (unsigned short)s; s += c; }
    for (i = 0; i + 3 < n; i += 4) { u32 v0=src[i],v1=src[i+1],v2=src[i+2],v3=src[i+3];
        dst[h1[(v0>>11)&2047]++]=v0; dst[h1[(v1>>11)&2047]++]=v1; dst[h1[(v2>>11)&2047]++]=v2; dst[h1[(v3>>11)&2047]++]=v3; }
    for (; i < n; i++) { u32 v = src[i]; dst[h1[(v>>11)&2047]++] = v; }
    src = a; dst = tmp;
    s = 0; for (int k = 0; k < 1024; k++) { unsigned c = h2[k]; h2[k] = (unsigned short)s; s += c; }
    for (i = 0; i < n; i++) { u32 v = src[i]; dst[h2[v>>22]++] = v; }
}

评测结果