代码

/* wc2017b1: fixed-stride MSD partition by the top byte (no counting pass: each
 * bucket gets n/256 + slack slots, its fill is recorded during the scatter),
 * then every bucket's low 24 bits are sorted in L3 by three fused 8-bit LSD
 * passes, the last one writing straight into the packed output position in `a`.
 * Overflow of a fixed bucket (adversarial data) falls back to the counting path. */
#include <stdlib.h>
#include <string.h>
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC push_options
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#endif

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

static void bucket_phase(unsigned *a, unsigned *tp, int m, unsigned *scr, unsigned *ap) {
    unsigned *__restrict__ scrp = scr;
    unsigned *__restrict__ app = ap;
    {   /* pass 0: count low byte, scatter tp -> scr, fuse byte-1 counts */
        memset(g_c0, 0, sizeof(g_c0));
        int i = 0;
        for (; i + 4 <= m; i += 4) {
            __builtin_prefetch(tp + i + 128);
            g_c0[tp[i] & 255u]++; g_c0[tp[i+1] & 255u]++; g_c0[tp[i+2] & 255u]++; g_c0[tp[i+3] & 255u]++;
        }
        for (; 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));
        i = 0;
        for (; i + 4 <= m; i += 4) {
            unsigned v0 = tp[i], v1 = tp[i+1], v2 = tp[i+2], v3 = tp[i+3];
            scrp[g_c0[v0 & 255u]++] = v0; g_c1[(v0 >> 8) & 255u]++;
            scrp[g_c0[v1 & 255u]++] = v1; g_c1[(v1 >> 8) & 255u]++;
            scrp[g_c0[v2 & 255u]++] = v2; g_c1[(v2 >> 8) & 255u]++;
            scrp[g_c0[v3 & 255u]++] = v3; g_c1[(v3 >> 8) & 255u]++;
        }
        for (; i < m; i++) { unsigned v = tp[i]; scrp[g_c0[v & 255u]++] = v; g_c1[(v >> 8) & 255u]++; }
    }
    {   /* pass 1: scatter scr -> tp, 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 = scrp[i]; tp[g_c1[(v >> 8) & 255u]++] = v; g_c2[(v >> 16) & 255u]++; }
    }
    {   /* pass 2: scatter tp -> a (final position) */
        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]; app[g_c2[(v >> 16) & 255u]++] = v; }
    }
}

void sort(unsigned *a, int n) {
    if (n <= 1) return;
    unsigned stride = (unsigned)((n + 255) / 256) + (unsigned)(n >> 9) + 4096;
    unsigned *tmp = (unsigned *)malloc((size_t)stride * 256u * 4u);
    if (!tmp) return;
    static unsigned fill[256];
    memset(fill, 0, sizeof(fill));
    int i = 0, of = 0;
    for (; i < n; i++) {
        unsigned v = a[i];
        unsigned b = v >> 24;
        unsigned f = fill[b];
        if (f >= stride) { of = 1; break; }
        tmp[(size_t)b * stride + f] = v;
        fill[b] = f + 1;
    }
    if (of) {
        /* adversarial distribution: redo with the exact counting partition */
        free(tmp);
        memset(g_c0, 0, sizeof(g_c0));
        for (int k = 0; k < n; k++) g_c0[a[k] >> 24]++;
        unsigned off2[257];
        unsigned s = 0, maxb = 0;
        for (int k = 0; k < 256; k++) { off2[k] = s; unsigned c = g_c0[k]; s += c; if (c > maxb) maxb = c; }
        off2[256] = s;
        unsigned *tmp2 = (unsigned *)malloc((size_t)n * 4);
        if (!tmp2) { free(tmp); return; }
        unsigned pos[256];
        memcpy(pos, off2, sizeof(pos));
        for (int k = 0; k < n; k++) { unsigned v = a[k]; tmp2[pos[v >> 24]++] = v; }
        unsigned *scr = (unsigned *)malloc((size_t)(maxb ? maxb : 1) * 4);
        if (!scr) { memcpy(a, tmp2, (size_t)n * 4); free(tmp2); return; }
        for (int b = 0; b < 256; b++) {
            int m = (int)(off2[b + 1] - off2[b]);
            if (m <= 0) continue;
            if (m == 1) { a[off2[b]] = tmp2[off2[b]]; continue; }
            bucket_phase(a, tmp2 + off2[b], m, scr, a + off2[b]);
        }
        free(scr); free(tmp2);
        return;
    }
    /* packed offsets */
    unsigned off[257];
    unsigned s = 0;
    for (int b = 0; b < 256; b++) { off[b] = s; s += fill[b]; }
    off[256] = s;
    unsigned maxb = 0;
    for (int b = 0; b < 256; b++) if (fill[b] > maxb) maxb = fill[b];
    unsigned *scr = (unsigned *)malloc((size_t)(maxb ? maxb : 1) * 4);
    if (!scr) return;   /* cannot finish: leave data partitioned (never happens in practice) */
    for (int b = 0; b < 256; b++) {
        int m = (int)fill[b];
        if (m <= 0) continue;
        unsigned *tp = tmp + (size_t)b * stride;
        if (m == 1) { a[off[b]] = tp[0]; continue; }
        bucket_phase(a, tp, m, scr, a + off[b]);
    }
    free(scr);
    free(tmp);
}
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC pop_options
#endif

评测结果