代码

// 1001b: sort n = 1<<27 unsigned. 4-pass LSD byte radix with fused histograms.
typedef unsigned u32;
static u32 tmpbuf[1 << 27];
static u32 h[4][256];

void sort(u32 *a, int n) {
    for (int i = 0; i < 256; i++) { h[0][i] = 0; h[1][i] = 0; h[2][i] = 0; h[3][i] = 0; }
    for (int i = 0; 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]++;
    }
    u32 *tmp = tmpbuf;
    u32 s = 0;
    for (int i = 0; i < 256; i++) { u32 c = h[0][i]; h[0][i] = s; s += c; }
    for (int i = 0; i < n; i++) { u32 v = a[i]; tmp[h[0][v & 255]++] = v; }
    s = 0;
    for (int i = 0; i < 256; i++) { u32 c = h[1][i]; h[1][i] = s; s += c; }
    for (int i = 0; i < n; i++) { u32 v = tmp[i]; a[h[1][(v >> 8) & 255]++] = v; }
    s = 0;
    for (int i = 0; i < 256; i++) { u32 c = h[2][i]; h[2][i] = s; s += c; }
    for (int i = 0; i < n; i++) { u32 v = a[i]; tmp[h[2][(v >> 16) & 255]++] = v; }
    s = 0;
    for (int i = 0; i < 256; i++) { u32 c = h[3][i]; h[3][i] = s; s += c; }
    for (int i = 0; i < n; i++) { u32 v = tmp[i]; a[h[3][v >> 24]++] = v; }
}

评测结果