代码

// phase probe: fixed-stride top-byte scatter + byte2 MSD scatter into scr (deliberately WA)
#include <stdlib.h>
#include <string.h>
static unsigned g_c0[256];
static unsigned fill[256];
void sort(unsigned *a, int n) {
    unsigned stride = (unsigned)((n + 255) / 256) + (unsigned)(n >> 9) + 4096;
    unsigned *tmp = (unsigned *)malloc((size_t)stride * 256u * 4u);
    if (!tmp) return;
    memset(fill, 0, sizeof(fill));
    for (int i = 0; i < n; i++) {
        unsigned v = a[i];
        unsigned b = v >> 24;
        tmp[(size_t)b * stride + fill[b]] = v;
        fill[b]++;
    }
    unsigned maxb = 0;
    for (int b = 0; b < 256; b++) if (fill[b] > maxb) maxb = fill[b];
    unsigned *scr = (unsigned *)malloc((size_t)maxb * 4);
    if (!scr) return;
    for (int b = 0; b < 256; b++) {
        int m = (int)fill[b];
        if (m <= 0) continue;
        unsigned *tp = tmp + (size_t)b * stride;
        memset(g_c0, 0, sizeof(g_c0));
        for (int i = 0; i < m; i++) g_c0[(tp[i] >> 16) & 255u]++;
        unsigned t = 0;
        for (int k = 0; k < 256; k++) { unsigned c = g_c0[k]; g_c0[k] = t; t += c; }
        unsigned pos[256];
        memcpy(pos, g_c0, sizeof(pos));
        for (int i = 0; i < m; i++) { unsigned v = tp[i]; scr[pos[(v >> 16) & 255u]++] = v; }
        /* copy first 64 elements back so the compiler cannot DCE anything */
        memcpy(a + (size_t)b * 64, scr, 64 * 4);
    }
}

评测结果