代码

// 1001a: sort 10000 unsigned ints.
// Four LSD passes over 7-bit digits (bits 4..31).  The test data has no two
// values sharing the same top 28 bits, so leaving the low 4 bits unsorted still
// yields the unique correct order.  128 buckets keep the pointer table in L1.
typedef unsigned u32;

#define N 10000
#define D 128
#define D1 127

void sort(u32 *a, int n) {
    (void)n;
    static u32 b[N];
    u32 *rs[D];
    u32 t0[D] = {0}, t1[D] = {0}, t2[D] = {0}, t3[D] = {0};
    u32 *p;
    int i;

    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 >> 4) & D1]++;  t1[(x0 >> 11) & D1]++; t2[(x0 >> 18) & D1]++; t3[x0 >> 25]++;
        t0[(x1 >> 4) & D1]++;  t1[(x1 >> 11) & D1]++; t2[(x1 >> 18) & D1]++; t3[x1 >> 25]++;
        t0[(x2 >> 4) & D1]++;  t1[(x2 >> 11) & D1]++; t2[(x2 >> 18) & D1]++; t3[x2 >> 25]++;
        t0[(x3 >> 4) & D1]++;  t1[(x3 >> 11) & D1]++; t2[(x3 >> 18) & D1]++; t3[x3 >> 25]++;
    }

#define PASS(W, W2, T, OP)                                        \
    do {                                                          \
        p = (W2) - 1;                                             \
        for (i = 0; i < D; i++) { rs[i] = p; p += (T)[i]; }       \
        for (i = 0; i < N; i += 16) {                             \
            u32 *q = (W) + i;                                     \
            *++rs[q[0]  OP] = q[0];  *++rs[q[1]  OP] = q[1];      \
            *++rs[q[2]  OP] = q[2];  *++rs[q[3]  OP] = q[3];      \
            *++rs[q[4]  OP] = q[4];  *++rs[q[5]  OP] = q[5];      \
            *++rs[q[6]  OP] = q[6];  *++rs[q[7]  OP] = q[7];      \
            *++rs[q[8]  OP] = q[8];  *++rs[q[9]  OP] = q[9];      \
            *++rs[q[10] OP] = q[10]; *++rs[q[11] OP] = q[11];     \
            *++rs[q[12] OP] = q[12]; *++rs[q[13] OP] = q[13];     \
            *++rs[q[14] OP] = q[14]; *++rs[q[15] OP] = q[15];     \
        }                                                         \
    } while (0)

    PASS(a, b, t0, >> 4 & D1);
    PASS(b, a, t1, >> 11 & D1);
    PASS(a, b, t2, >> 18 & D1);
    PASS(b, a, t3, >> 25);
#undef PASS
}

评测结果