代码

// 16-bit 2-pass line-buffer (staging + memcpy flush), port to n=1e8
#include <string.h>
typedef unsigned int u32;
typedef unsigned char u8;
static u32 tmp[100000000];
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++) { __builtin_prefetch(&src[i+256],0,0); 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++) {
            __builtin_prefetch(&src[base+i+256],0,0);
            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];
                memcpy(&dst[go], &staging[b * 16], 64);
                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];
            memcpy(&dst[go], &staging[j * 16], p * 4);
        }
    }
}
void sort(unsigned *aa, int n) {
    u32 *a = (u32*)aa;
    radix16_pass(a, tmp, n, 0);
    radix16_pass(tmp, a, n, 16);
}

评测结果