代码

// 1001b: sort n = 1<<27 unsigned.
// In-place MSD/LSD hybrid: partition by the top byte with an American-flag
// permutation directly inside `a` (no 512 MB temp -> no ~131k first-touch page
// faults and no second 512 MB write stream), then finish each ~2 MB bucket with
// cache-resident LSD passes using two 4 MB scratch buffers.
typedef unsigned u32;

static u32 S1[1 << 20], S2[1 << 20];      // 4 MB + 4 MB in-cache scratch
static u32 cnt[256], nxt[256], bstart[257];

#define BUCKET_LIMIT (1 << 20)            // elements sortable from scratch (4 MB)

// sort by the low `bytes` bytes of every element (higher bytes are already equal)
static void lsd_low(u32 *p, int len, int bytes) {
    static u32 h[4][256];
    if (len <= 1 || bytes <= 0) return;
    if (bytes == 1) {
        for (int i = 0; i < 256; i++) h[0][i] = 0;
        for (int i = 0; i < len; i++) h[0][p[i] & 255]++;
        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 < len; i++) { u32 v = p[i]; S1[h[0][v & 255]++] = v; }
        for (int i = 0; i < len; i++) p[i] = S1[i];
        return;
    }
    u32 *src = p;
    for (int pass = 0; pass < bytes; pass++) {
        int sh = pass * 8;
        for (int i = 0; i < 256; i++) h[pass][i] = 0;
        for (int i = 0; i < len; i++) h[pass][(src[i] >> sh) & 255]++;
        u32 s = 0;
        for (int i = 0; i < 256; i++) { u32 c = h[pass][i]; h[pass][i] = s; s += c; }
        u32 *d = (pass + 1 == bytes) ? p : ((pass & 1) ? S2 : S1);
        for (int i = 0; i < len; i++) { u32 v = src[i]; d[h[pass][(v >> sh) & 255]++] = v; }
        src = d;
    }
}

// in-place American-flag partition of p[0..len) by the byte at `shift`
static void msd_partition(u32 *p, int len, int shift) {
    for (int i = 0; i < 256; i++) cnt[i] = 0;
    for (int i = 0; i < len; i++) cnt[(p[i] >> shift) & 255]++;
    u32 s = 0;
    for (int i = 0; i < 256; i++) { bstart[i] = s; nxt[i] = s; s += cnt[i]; }
    bstart[256] = s;
    for (int b = 0; b < 256; b++) {
        u32 end = bstart[b + 1];
        while (nxt[b] < end) {
            u32 v = p[nxt[b]];
            u32 vb = (v >> shift) & 255;
            if (vb == b) { nxt[b]++; }
            else { u32 w = p[nxt[vb]]; p[nxt[b]] = w; p[nxt[vb]++] = v; }
        }
    }
}

// bits above `shift` are already correct
static void radix_rec(u32 *p, int len, int shift) {
    if (len <= 1) return;
    if (len <= BUCKET_LIMIT || shift <= 0) { lsd_low(p, len, shift >> 3); return; }
    msd_partition(p, len, shift - 8);
    for (int b = 0; b < 256; b++) {
        int l = (int)(bstart[b + 1] - bstart[b]);
        if (l > 1) radix_rec(p + bstart[b], l, shift - 8);
    }
}

void sort(u32 *a, int n) {
    radix_rec(a, n, 32);
}

评测结果