代码

// 1001b: sort n = 1<<27 unsigned.
// Two-level top partition with only 16 write streams per DRAM pass:
//   pass 1  a -> TMP  partitioned by the top nibble      (16 streams)
//   pass 2  TMP -> a  partitioned by the next nibble     (16 streams per broad bucket)
//   pass 3  each ~2 MB fine bucket sorted in L3 (LSD over the low 24 bits)
// Rationale: on this duck a 256-stream scattered pass costs ~8 ns/element while
// stream count is what hurts, so two cheap 16-stream passes beat one 256-stream pass.
typedef unsigned u32;

static u32 TMP[1 << 27];                 // 512 MB
static u32 S1[1 << 21], S2[1 << 21];     // 8 MB + 8 MB scratch (bucket limit 2M elements)
static u32 fstart[257];

#define BUCKET_LIMIT (1 << 21)

// sort by the low `bytes` bytes; higher bytes are already equal. Ends in place.
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;
    }
}

// fallback for a too-large fine bucket: plain LSD over the low 24 bits using TMP
static void lsd_big(u32 *p, int len) {
    static u32 h[3][256];
    u32 *src = p, *dst = TMP;
    for (int pass = 0; pass < 3; 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 == 2) ? p : dst;
        for (int i = 0; i < len; i++) { u32 v = src[i]; d[h[pass][(v >> sh) & 255]++] = v; }
        src = d; dst = (d == TMP) ? p : TMP;
    }
}

void sort(u32 *a, int n) {
    // ---- pass 1: a -> TMP by the top nibble (16 streams)
    u32 c[16], st[17];
    for (int i = 0; i < 16; i++) c[i] = 0;
    for (int i = 0; i < n; i++) c[a[i] >> 28]++;
    u32 s = 0;
    for (int i = 0; i < 16; i++) { u32 cc = c[i]; st[i] = s; c[i] = s; s += cc; }
    st[16] = s;
    for (int i = 0; i < n; i++) { u32 v = a[i]; TMP[c[v >> 28]++] = v; }

    // ---- pass 2: TMP -> a by the next nibble (16 streams inside each broad bucket)
    for (int b = 0; b < 16; b++) {
        u32 lo = st[b], hi = st[b + 1];
        int len = (int)(hi - lo);
        u32 c2[16];
        for (int i = 0; i < 16; i++) c2[i] = 0;
        for (int i = 0; i < len; i++) c2[(TMP[lo + i] >> 24) & 15]++;
        u32 t = 0;
        for (int i = 0; i < 16; i++) { u32 cc = c2[i]; fstart[(b << 4) + i] = lo + t; c2[i] = t; t += cc; }
        if (len <= 0) continue;
        u32 *src = TMP + lo, *dst = a + lo;
        for (int i = 0; i < len; i++) { u32 v = src[i]; dst[c2[(v >> 24) & 15]++] = v; }
    }
    fstart[256] = (u32)n;

    // ---- pass 3: finish each fine bucket in L3 over the low 24 bits
    for (int i = 0; i < 256; i++) {
        int len = (int)(fstart[i + 1] - fstart[i]);
        if (len <= 1) continue;
        u32 *p = a + fstart[i];
        if (len <= BUCKET_LIMIT) lsd_low(p, len, 3);
        else lsd_big(p, len);
    }
}

评测结果