代码

#include <string.h>
typedef unsigned int u32;
typedef unsigned char u8;
static u32 tmp[1 << 27];
static u32 cnt[2048];
static u8 pos[2048];
static u32 staging[2048 * 16];
static void radix_pass(u32 *src, u32 *dst, int n, int shift, int mask) {
    int i, j;
    for (j = 0; j < 2048; j++) cnt[j] = 0;
    for (i = 0; i < n; i++) { __builtin_prefetch(&src[i+256],0,0); cnt[(src[i] >> shift) & mask]++; }
    { u32 t = 0; for (j = 0; j < 2048; j++) { u32 c = cnt[j]; cnt[j] = t; t += c; } }
    for (j = 0; j < 2048; j++) pos[j] = 0;
    for (i = 0; i < n; i++) {
        __builtin_prefetch(&src[i+256],0,0);
        u32 x = src[i];
        u32 b = (x >> shift) & mask;
        u32 p = pos[b];
        staging[b * 16 + p] = x;
        p++;
        if (p == 16) { u32 go = cnt[b]; memcpy(&dst[go], &staging[b * 16], 64); cnt[b] = go + 16; p = 0; }
        pos[b] = (u8)p;
    }
    for (j = 0; j < 2048; j++) { u32 p = pos[j]; if (p > 0) { u32 go = cnt[j]; memcpy(&dst[go], &staging[j * 16], p * 4); } }
}
void sort(unsigned *aa, int n) {
    u32 *a = (u32*)aa;
    radix_pass(a, tmp, n, 0, 2047);
    radix_pass(tmp, a, n, 11, 2047);
    radix_pass(a, tmp, n, 22, 1023);
    for (int i = 0; i < n; i++) a[i] = tmp[i];
}

评测结果