代码

// 1001b: sort n = 1<<27 unsigned.
// Cache-blocked radix: partition by the top byte into a big temp, then sort
// each ~2MB bucket entirely in L3 with 3 byte-level LSD passes whose last
// pass writes straight into the output array.
typedef unsigned u32;

static u32 TMP[1 << 27];      // 512 MB
static u32 SCRATCH[1 << 20];  // 4 MB, in-cache scratch
static u32 CNT[256], START[256];

static void lsd4(u32 *a, int n) {
    static u32 h[4][256];
    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 *t = TMP;
    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]; t[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 = t[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]; t[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 = t[i]; a[h[3][v >> 24]++] = v; }
}

static void sort_bucket(u32 *p, int len, u32 *out) {
    u32 *src = p, *dst = SCRATCH;
    for (int pass = 0; pass < 3; pass++) {
        int sh = pass * 8;
        for (int i = 0; i < 256; i++) CNT[i] = 0;
        for (int i = 0; i < len; i++) CNT[(src[i] >> sh) & 255]++;
        u32 s = 0;
        for (int i = 0; i < 256; i++) { u32 c = CNT[i]; CNT[i] = s; s += c; }
        u32 *d = (pass == 2) ? out : dst;
        for (int i = 0; i < len; i++) { u32 v = src[i]; d[CNT[(v >> sh) & 255]++] = v; }
        src = d;
        dst = (d == SCRATCH) ? p : SCRATCH;
    }
}

void sort(u32 *a, int n) {
    for (int i = 0; i < 256; i++) CNT[i] = 0;
    for (int i = 0; i < n; i++) CNT[a[i] >> 24]++;
    int ok = 1;
    for (int i = 0; i < 256; i++) if (CNT[i] > (1 << 20)) ok = 0;
    if (!ok) { lsd4(a, n); return; }
    u32 s = 0;
    for (int i = 0; i < 256; i++) { u32 c = CNT[i]; START[i] = s; CNT[i] = s; s += c; }
    for (int i = 0; i < n; i++) { u32 v = a[i]; TMP[CNT[v >> 24]++] = v; }
    for (int b = 0; b < 256; b++) {
        int len = (int)((b < 255 ? START[b + 1] : (u32)n) - START[b]);
        if (len == 0) continue;
        u32 *p = TMP + START[b], *o = a + START[b];
        if (len == 1) { o[0] = p[0]; continue; }
        sort_bucket(p, len, o);
    }
}

评测结果