代码

/* wc2017b1: MSD partition by the top byte (one scatter a->tmp), then sort each
 * ~3MB bucket in L3 with three fused low-byte LSD passes, the last one writing
 * straight into `a`.  DRAM traffic ~4 traversals instead of ~7. */
#include <stdlib.h>
#include <string.h>

static unsigned g_c0[256], g_c1[256], g_c2[256];

void sort(unsigned *a, int n) {
    if (n <= 1) return;
    unsigned *tmp = (unsigned *)malloc((size_t)n * 4);
    if (!tmp) return;
    memset(g_c0, 0, sizeof(g_c0));
    for (int i = 0; i < n; i++) g_c0[a[i] >> 24]++;
    unsigned off[257];
    unsigned s = 0, maxb = 0;
    for (int k = 0; k < 256; k++) {
        off[k] = s;
        unsigned c = g_c0[k];
        s += c;
        if (c > maxb) maxb = c;
    }
    off[256] = s;
    {
        unsigned pos[256];
        memcpy(pos, off, sizeof(pos));
        for (int i = 0; i < n; i++) { unsigned v = a[i]; tmp[pos[v >> 24]++] = v; }
    }
    unsigned *scr = (unsigned *)malloc((size_t)(maxb ? maxb : 1) * 4);
    if (!scr) { memcpy(a, tmp, (size_t)n * 4); free(tmp); return; }
    for (int b = 0; b < 256; b++) {
        unsigned bs = off[b], be = off[b + 1];
        int m = (int)(be - bs);
        if (m <= 1) { if (m == 1) a[bs] = tmp[bs]; continue; }
        unsigned *__restrict__ tp = tmp + bs;
        unsigned *__restrict__ ap = a + bs;
        {   /* pass 0: count low byte, scatter tmp -> scr, fuse byte-1 counts */
            memset(g_c0, 0, sizeof(g_c0));
            for (int i = 0; i < m; i++) g_c0[tp[i] & 255u]++;
            unsigned t = 0;
            for (int k = 0; k < 256; k++) { unsigned c = g_c0[k]; g_c0[k] = t; t += c; }
            memset(g_c1, 0, sizeof(g_c1));
            for (int i = 0; i < m; i++) { unsigned v = tp[i]; scr[g_c0[v & 255u]++] = v; g_c1[(v >> 8) & 255u]++; }
        }
        {   /* pass 1: scatter scr -> tmp, fuse byte-2 counts */
            unsigned t = 0;
            for (int k = 0; k < 256; k++) { unsigned c = g_c1[k]; g_c1[k] = t; t += c; }
            memset(g_c2, 0, sizeof(g_c2));
            for (int i = 0; i < m; i++) { unsigned v = scr[i]; tp[g_c1[(v >> 8) & 255u]++] = v; g_c2[(v >> 16) & 255u]++; }
        }
        {   /* pass 2: scatter tmp -> a */
            unsigned t = 0;
            for (int k = 0; k < 256; k++) { unsigned c = g_c2[k]; g_c2[k] = t; t += c; }
            for (int i = 0; i < m; i++) { unsigned v = tp[i]; ap[g_c2[(v >> 16) & 255u]++] = v; }
        }
    }
    free(scr);
    free(tmp);
}

评测结果