代码

#include <string.h>
#include <stdint.h>
typedef unsigned int u32;
typedef unsigned char u8;
static u32 tmp[(1u<<27) + (1u<<21)] __attribute__((aligned(64)));
static u32 cnt[65536];
static u32 rbase[65536];
static u32 pbase[65536];
static u32 off[65536];
static u8 pos[65536];
static u32 staging[65536 * 16] __attribute__((aligned(64)));
static void radix16_top(u32 *src, u32 *dst, int n) {
    int i, j;
    for (j = 0; j < 65536; j++) cnt[j] = 0;
    for (i = 0; i < n; i++) { __builtin_prefetch(&src[i+256],0,0); cnt[src[i] >> 16]++; }
    { u32 t = 0, p = 0; for (j = 0; j < 65536; j++) { u32 c = cnt[j]; rbase[j] = t; pbase[j] = p; t += c; p = (p + c + 15) & ~15u; } }
    for (j = 0; j < 65536; j++) { off[j] = pbase[j]; pos[j] = 0; }
    for (i = 0; i < n; i++) {
        __builtin_prefetch(&src[i+256],0,0);
        u32 x = src[i]; u32 b = x >> 16; u32 p = pos[b];
        staging[b * 16 + p] = x; p++;
        if (p == 16) { u32 go = off[b]; __builtin_memcpy(dst+go, staging+b*16, 64); off[b] = go + 16; p = 0; }
        pos[b] = (u8)p;
    }
    for (j = 0; j < 65536; j++) { u32 p = pos[j]; if (p > 0) memcpy(dst+off[j], staging+j*16, p*4); }
}
void sort(unsigned *aa, int n) { radix16_top((u32*)aa, tmp, n); }

评测结果