代码

// Compressed-intermediate MSD radix sort [8][8][16] for problem 1001 (n=1e8 u32, uniform).
// Pass 1: bucket by top-8, store ONLY low-24 bits (3 byte planes = 300MB vs 400MB full u32).
// Pass 2: per top-8 bucket, greedy in-place swap to group by byte2 (bits 16-23).
// Pass 3: per (top8,byte2) sub-bucket, 2x8-bit LSD of low-16, reconstruct u32, NT-flush to a[].
#include <immintrin.h>
#include <string.h>
#include <emmintrin.h>

typedef unsigned int u32;
typedef unsigned char u8;
typedef unsigned short u16;

#ifndef N
#define N 100000000
#endif
#ifndef TMP_CAP
#define TMP_CAP 400000
#endif

static u8 s0[N] __attribute__((aligned(64)));
static u8 s1[N] __attribute__((aligned(64)));
static u8 s2[N] __attribute__((aligned(64)));

static u32 cnt[256];
static u32 B[257];
static u32 used[256];

static u32 c2[256];
static u32 start2[256];
static u32 next2[256];

static u32 h16[256];
static u32 h8[256];
static u16 tmp16[TMP_CAP] __attribute__((aligned(64)));
static u32 tmp32[TMP_CAP] __attribute__((aligned(64)));

__attribute__((target("sse2")))
static inline void flush_range_nt(u32 *dst, const u32 *src, int m) {
    int mi = 0;
    while ((((unsigned long)(dst + mi)) & 15) && mi < m) { dst[mi] = src[mi]; mi++; }
    for (; mi + 4 <= m; mi += 4) {
        __m128i v = _mm_loadu_si128((const __m128i*)(src + mi));
        _mm_stream_si128((__m128i*)(dst + mi), v);
    }
    for (; mi < m; mi++) dst[mi] = src[mi];
}

// Sort low-16 bits of sub-bucket [lo, hi) (top byte k, byte2 g fixed), write to a[dst..].
static void sort16(u32 *a, u32 dst_base, u32 k, u32 g, u32 lo, u32 hi) {
    u32 m = hi - lo;
    int i, j;
    for (j = 0; j < 256; j++) h16[j] = 0;
    for (i = lo; i < (int)hi; i++) h16[s0[i]]++;
    for (j = 1; j < 256; j++) h16[j] += h16[j-1];
    for (i = (int)hi - 1; i >= (int)lo; i--) tmp16[--h16[s0[i]]] = (u16)((s1[i] << 8) | s0[i]);
    for (j = 0; j < 256; j++) h8[j] = 0;
    for (i = 0; i < (int)m; i++) h8[tmp16[i] >> 8]++;
    for (j = 1; j < 256; j++) h8[j] += h8[j-1];
    u32 base = ((k << 24) | (g << 16));
    for (i = (int)m - 1; i >= 0; i--) tmp32[--h8[tmp16[i] >> 8]] = base | tmp16[i];
    flush_range_nt(a + dst_base, tmp32, m);
}

void sort(unsigned *aa, int n) {
    u32 *a = (u32*)aa;
    int i, j;
    (void)n;

    // ---- Pass 1: histogram top-8 + compressed scatter ----
    for (j = 0; j < 256; j++) cnt[j] = 0;
    for (i = 0; i < N; i++) cnt[a[i] >> 24]++;
    { u32 acc = 0; B[0] = 0; for (j = 0; j < 256; j++) { acc += cnt[j]; B[j+1] = acc; } }
    for (j = 0; j < 256; j++) used[j] = B[j];
    for (i = 0; i < N; i++) {
        u32 x = a[i];
        u32 k = x >> 24;
        u32 p = used[k]++;
        s0[p] = (u8)x;
        s1[p] = (u8)(x >> 8);
        s2[p] = (u8)(x >> 16);
    }

    // ---- Pass 2: per bucket, group by byte2 (in-place greedy swap) ----
    for (int k = 0; k < 256; k++) {
        u32 lo = B[k], hi = B[k+1];
        u32 m = hi - lo;
        if (m == 0) continue;
        for (j = 0; j < 256; j++) c2[j] = 0;
        for (i = (int)lo; i < (int)hi; i++) c2[s2[i]]++;
        { u32 acc = lo; for (j = 0; j < 256; j++) { start2[j] = acc; next2[j] = acc; acc += c2[j]; } }
        // greedy swap
        for (i = (int)lo; i < (int)hi; i++) {
            u32 g = s2[i];
            while ((u32)i < start2[g] || (u32)i >= start2[g] + c2[g]) {
                u32 jj = next2[g]++;
                u8 t0 = s0[i]; s0[i] = s0[jj]; s0[jj] = t0;
                u8 t1 = s1[i]; s1[i] = s1[jj]; s1[jj] = t1;
                u8 t2 = s2[i]; s2[i] = s2[jj]; s2[jj] = t2;
                g = s2[i];
            }
            if (next2[g] <= (u32)i) next2[g] = (u32)i + 1;
        }
        // ---- Pass 3: per byte2 group, sort low-16 + reconstruct ----
        for (j = 0; j < 256; j++) {
            u32 c = c2[j];
            if (c == 0) continue;
            u32 gl = start2[j];
            sort16(a, start2[j], (u32)k, (u32)j, gl, gl + c);
        }
    }
}

评测结果