代码

/* wc2017b1: MSD by top byte, then per-bucket 12+12-bit LSD (2 passes). */
#include <stdlib.h>
#include <string.h>

static unsigned g_c0[4096], g_c1[4096];

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 12 bits, scatter tmp -> scr, fuse high-12 counts */
            memset(g_c0, 0, sizeof(g_c0));
            for (int i = 0; i < m; i++) g_c0[tp[i] & 4095u]++;
            unsigned t = 0;
            for (int k = 0; k < 4096; 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 & 4095u]++] = v; g_c1[(v >> 12) & 4095u]++; }
        }
        {   /* pass 1: scatter scr -> a (top 12 bits of the low 24) */
            unsigned t = 0;
            for (int k = 0; k < 4096; k++) { unsigned c = g_c1[k]; g_c1[k] = t; t += c; }
            for (int i = 0; i < m; i++) { unsigned v = scr[i]; ap[g_c1[(v >> 12) & 4095u]++] = v; }
        }
    }
    free(scr);
    free(tmp);
}

评测结果