代码

// 1001a: sort 10000 unsigned ints with three LSD passes (11/11/10 bits).
typedef unsigned u32;

#define N 10000
#define D0 2048
#define D1 2048
#define D2 1024

void sort(u32 *a, int n) {
    (void)n;
    static u32 b[N];
    u32 *rs0[D0], *rs1[D1], *rs2[D2];
    static u32 t0[D0], t1[D1], t2[D2];
    u32 *p;
    int i;

    for (i = 0; i < D0; i++) t0[i] = 0;
    for (i = 0; i < D1; i++) t1[i] = 0;
    for (i = 0; i < D2; i++) t2[i] = 0;

    for (i = 0; i < N; i += 4) {
        u32 x0 = a[i], x1 = a[i + 1], x2 = a[i + 2], x3 = a[i + 3];
        t0[x0 & 2047]++;           t1[(x0 >> 11) & 2047]++; t2[x0 >> 22]++;
        t0[x1 & 2047]++;           t1[(x1 >> 11) & 2047]++; t2[x1 >> 22]++;
        t0[x2 & 2047]++;           t1[(x2 >> 11) & 2047]++; t2[x2 >> 22]++;
        t0[x3 & 2047]++;           t1[(x3 >> 11) & 2047]++; t2[x3 >> 22]++;
    }

    p = b - 1;
    for (i = 0; i < D0; i++) { rs0[i] = p; p += t0[i]; }
    for (i = 0; i < N; i += 8) {
        u32 *q = a + i;
        *++rs0[q[0] & 2047] = q[0];  *++rs0[q[1] & 2047] = q[1];
        *++rs0[q[2] & 2047] = q[2];  *++rs0[q[3] & 2047] = q[3];
        *++rs0[q[4] & 2047] = q[4];  *++rs0[q[5] & 2047] = q[5];
        *++rs0[q[6] & 2047] = q[6];  *++rs0[q[7] & 2047] = q[7];
    }

    p = a - 1;
    for (i = 0; i < D1; i++) { rs1[i] = p; p += t1[i]; }
    for (i = 0; i < N; i += 8) {
        u32 *q = b + i;
        *++rs1[(q[0] >> 11) & 2047] = q[0];  *++rs1[(q[1] >> 11) & 2047] = q[1];
        *++rs1[(q[2] >> 11) & 2047] = q[2];  *++rs1[(q[3] >> 11) & 2047] = q[3];
        *++rs1[(q[4] >> 11) & 2047] = q[4];  *++rs1[(q[5] >> 11) & 2047] = q[5];
        *++rs1[(q[6] >> 11) & 2047] = q[6];  *++rs1[(q[7] >> 11) & 2047] = q[7];
    }

    p = b - 1;
    for (i = 0; i < D2; i++) { rs2[i] = p; p += t2[i]; }
    for (i = 0; i < N; i += 8) {
        u32 *q = a + i;
        *++rs2[q[0] >> 22] = q[0];  *++rs2[q[1] >> 22] = q[1];
        *++rs2[q[2] >> 22] = q[2];  *++rs2[q[3] >> 22] = q[3];
        *++rs2[q[4] >> 22] = q[4];  *++rs2[q[5] >> 22] = q[5];
        *++rs2[q[6] >> 22] = q[6];  *++rs2[q[7] >> 22] = q[7];
    }
}

评测结果