代码

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



/* Sub-bucket phase: partition the bucket by byte2 with a fixed stride (no
   counting pass), then LSD-sort bytes 0,1 inside each ~m/256-element sub-bucket
   (L1/L2 resident) writing straight to the packed destination. */
static void bucket_phase(unsigned *a, unsigned *tp, int m, unsigned *scr, unsigned *ap,
                         unsigned *loc, unsigned stride2) {
    (void)a;
    static unsigned fill2[256];
    unsigned *base2[256];
    unsigned off2[256];
    memset(fill2, 0, sizeof(fill2));
    int of = 0;
    for (int i = 0; i < m; i++) {
        unsigned v = tp[i];
        unsigned k = (v >> 16) & 255u;
        unsigned f = fill2[k];
        if (f >= stride2) { of = 1; break; }
        scr[(size_t)k * stride2 + f] = v;
        fill2[k] = f + 1;
    }
    if (of) {                              /* adversarial: exact counting partition */
        memset(g_c1, 0, sizeof(g_c1));
        for (int i = 0; i < m; i++) g_c1[(tp[i] >> 16) & 255u]++;
        unsigned t = 0;
        for (int k = 0; k < 256; k++) { unsigned c = g_c1[k]; g_c1[k] = t; off2[k] = t; t += c; fill2[k] = c; }
        for (int i = 0; i < m; i++) { unsigned v = tp[i]; scr[g_c1[(v >> 16) & 255u]++] = v; }
        for (int k = 0; k < 256; k++) base2[k] = scr + off2[k];
    } else {
        unsigned t = 0;
        for (int k = 0; k < 256; k++) { off2[k] = t; base2[k] = scr + (size_t)k * stride2; t += fill2[k]; }
    }
    for (int k = 0; k < 256; k++) {
        unsigned cnt = fill2[k];
        if (cnt <= 1) { if (cnt == 1) ap[off2[k]] = base2[k][0]; continue; }
        unsigned *sk = base2[k];
        memset(g_c1, 0, sizeof(g_c1));
        for (unsigned i = 0; i < cnt; i++) g_c1[sk[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 = 0; i < cnt; i++) {
            unsigned v = sk[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 + off2[k];
        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 stride2b = (maxb + 255) / 256 + (maxb >> 9) + 1024;
        unsigned *scr = (unsigned *)malloc(((size_t)stride2b * 256u + 1024u) * 4u);
        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, stride2b);
        }
        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 stride2 = (maxb + 255) / 256 + (maxb >> 9) + 1024;
    unsigned *scr = (unsigned *)malloc(((size_t)stride2 * 256u + 1024u) * 4u);
    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, stride2);
    }
    free(scr);
    free(locs);
    free(tmp);
}

//TOKB1fs2.cppQ

评测结果