代码

// 1001b: cache-blocked radix with staged (sequential-ish) first-level scatter.
typedef unsigned u32;
static u32 TMP[1 << 27];
static u32 SCRATCH[1 << 20];
static u32 CNT[256], START[256];
static u32 STAGE[256][256];
static u32 scnt[256];
#define BLK 32768

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) || CNT[i] > 256 * (n / BLK + 2)) ok = 0;
    if (!ok) {  // fallback: plain LSD into TMP
        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 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; }
        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 < 256; i++) scnt[i] = 0;
    for (int base = 0; base < n; base += BLK) {
        int blk = n - base; if (blk > BLK) blk = BLK;
        for (int i = 0; i < blk; i++) {
            u32 v = a[base + i];
            u32 b = v >> 24;
            STAGE[b][scnt[b]++] = v;
        }
        for (int b = 0; b < 256; b++) {
            u32 c = scnt[b];
            if (!c) continue;
            u32 *d = TMP + CNT[b];
            u32 *sg = STAGE[b];
            for (u32 k = 0; k < c; k++) d[k] = sg[k];
            CNT[b] += c;
            scnt[b] = 0;
        }
    }
    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);
    }
}

评测结果