代码

/* wc2017b1: MSD by the top 10 bits (1024 buckets), then each ~780KB bucket is
 * sorted in L3 with 8/8/6-bit LSD passes writing straight into `a`. */
#include <stdlib.h>
#include <string.h>

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

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] >> 22]++;
    unsigned off[1025];
    unsigned s = 0, maxb = 0;
    for (int k = 0; k < 1024; k++) {
        off[k] = s;
        unsigned c = g_c0[k];
        s += c;
        if (c > maxb) maxb = c;
    }
    off[1024] = s;
    {
        unsigned pos[1024];
        memcpy(pos, off, sizeof(pos));
        for (int i = 0; i < n; i++) { unsigned v = a[i]; tmp[pos[v >> 22]++] = 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 < 1024; 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) & 63u]++; }
        }
        {   /* pass 2: scatter tmp -> a */
            unsigned t = 0;
            for (int k = 0; k < 64; 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) & 63u]++] = v; }
        }
    }
    free(scr);
    free(tmp);
}

评测结果