代码

/* 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>

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 *loc) {
    /* pass 0: count byte0 and scatter tp -> scr into 256 contiguous byte0 sub-buckets */
    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; }
    }
    /* now each byte0 sub-bucket is ~m/256 (~8KB) and lives in L1/L2: LSD by bytes 1 and 2
       straight into the packed destination, no more full-bucket passes */
    for (int k = 0; k < 256; k++) {
        unsigned s0 = g_c0[k];
        unsigned s1 = (k == 255) ? (unsigned)m : g_c0[k + 1];
        unsigned cnt = s1 - s0;
        if (cnt <= 1) { if (cnt == 1) ap[s0] = scr[s0]; continue; }
        {
            /* LSD over the remaining 16 bits: byte0 (least significant) first, then byte1 */
            memset(g_c1, 0, sizeof(g_c1));
            for (unsigned i = s0; i < s1; i++) g_c1[scr[i] & 255u]++;
            unsigned t2 = 0;
            for (int q = 0; q < 256; q++) { unsigned c = g_c1[q]; g_c1[q] = t2; t2 += c; }
            memset(g_c2, 0, sizeof(g_c2));
            for (unsigned i = s0; i < s1; i++) {
                unsigned v = scr[i];
                loc[g_c1[v & 255u]++] = v;
                g_c2[(v >> 8) & 255u]++;
            }
            t2 = 0;
            for (int q = 0; q < 256; q++) { unsigned c = g_c2[q]; g_c2[q] = t2; t2 += c; }
            unsigned *d = ap + s0;
            for (unsigned i = 0; i < cnt; i++) { unsigned v = loc[i]; d[g_c2[(v >> 8) & 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);
        unsigned *locs2 = (unsigned *)malloc((size_t)(maxb ? maxb : 1) * 4);
        if (!scr || !locs2) { 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], locs2);
        }
        free(scr); free(locs2); 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);
    unsigned *locs = (unsigned *)malloc((size_t)(maxb ? maxb : 1) * 4);
    if (!scr || !locs) 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], locs);
    }
    free(scr);
    free(locs);
    free(tmp);
}

评测结果