代码

typedef unsigned int u32;
typedef unsigned char u8;
static u32 tmp[1 << 27];
static u32 cnt[65536];
static u8 pos[65536];
static u32 staging[65536 * 16];

static void radix16_pass(u32 *src, u32 *dst, int n, int shift) {
    int i, j;
    for (j = 0; j < 65536; j++) cnt[j] = 0;
    for (i = 0; i < n; i++) cnt[(src[i] >> shift) & 0xffff]++;
    { u32 t = 0; for (j = 0; j < 65536; j++) { u32 c = cnt[j]; cnt[j] = t; t += c; } }
    for (j = 0; j < 65536; j++) pos[j] = 0;
    const int B = 1 << 20;
    for (int base = 0; base < n; base += B) {
        int len = (base + B < n) ? B : (n - base);
        for (i = 0; i < len; i++) {
            u32 x = src[base + i];
            u32 b = (x >> shift) & 0xffff;
            u32 p = pos[b];
            staging[b * 16 + p] = x;
            p++;
            if (p == 16) {
                u32 go = cnt[b];
                u32 *s = &staging[b * 16];
                for (int k = 0; k < 16; k++) dst[go + k] = s[k];
                cnt[b] = go + 16;
                p = 0;
            }
            pos[b] = (u8)p;
        }
    }
    for (j = 0; j < 65536; j++) {
        u32 p = pos[j];
        if (p > 0) {
            u32 go = cnt[j];
            u32 *s = &staging[j * 16];
            for (u32 k = 0; k < p; k++) dst[go + k] = s[k];
        }
    }
}

void sort(unsigned *aa, int n) {
    u32 *a = (u32*)aa;
    radix16_pass(a, tmp, n, 0);
    radix16_pass(tmp, a, n, 16);
}

评测结果