代码

#include <string.h>
typedef unsigned int u32;
typedef unsigned char u8;

#define NB 65536
#define LINE 32

static u32 tmp[134217728 + NB * LINE] __attribute__((aligned(64)));
static u32 staging[NB * LINE] __attribute__((aligned(64)));
static u32 cnt1[NB];
static u32 cnt2[NB];
static u32 base1[NB];
static u32 off[NB];
static u8  pos[NB];

static void pass1(u32 *src, u32 *dst, int n) {
    int i, j;
    for (j = 0; j < NB; j++) cnt1[j] = 0;
    int n8 = n & ~7;
    for (i = 0; i < n8; i += 8) {
        cnt1[src[i]&0xffff]++; cnt1[src[i+1]&0xffff]++; cnt1[src[i+2]&0xffff]++; cnt1[src[i+3]&0xffff]++;
        cnt1[src[i+4]&0xffff]++; cnt1[src[i+5]&0xffff]++; cnt1[src[i+6]&0xffff]++; cnt1[src[i+7]&0xffff]++;
    }
    for (; i < n; i++) cnt1[src[i] & 0xffff]++;
    { u32 p = 0; for (j = 0; j < NB; j++) { u32 c = cnt1[j]; base1[j] = p; off[j] = p; pos[j] = 0; p = (p + c + 31) & ~31u; } }
#define P1(X) do { u32 x_ = (X); u32 b_ = x_ & 0xffff; u32 p_ = pos[b_]; \
    staging[b_ * LINE + p_] = x_; p_++; \
    if (p_ == LINE) { u32 go_ = off[b_]; memcpy(dst + go_, staging + b_ * LINE, 128); off[b_] = go_ + LINE; p_ = 0; } \
    pos[b_] = (u8)p_; } while (0)
    int n8s = n & ~7;
    for (i = 0; i < n8s; i += 8) {
        P1(src[i]); P1(src[i+1]); P1(src[i+2]); P1(src[i+3]);
        P1(src[i+4]); P1(src[i+5]); P1(src[i+6]); P1(src[i+7]);
    }
    for (; i < n; i++) P1(src[i]);
#undef P1
    for (j = 0; j < NB; j++) { u32 p = pos[j]; if (p > 0) memcpy(dst + off[j], staging + j * LINE, p * 4); }
}

static void pass2(u32 *src, u32 *dst, int n) {
    int i, j;
    for (j = 0; j < NB; j++) cnt2[j] = 0;
    for (j = 0; j < NB; j++) {
        u32 c = cnt1[j];
        if (c == 0) continue;
        u32 *s = src + base1[j];
        int c8 = (int)c & ~7;
        for (i = 0; i < c8; i += 8) {
            cnt2[s[i]>>16]++; cnt2[s[i+1]>>16]++; cnt2[s[i+2]>>16]++; cnt2[s[i+3]>>16]++;
            cnt2[s[i+4]>>16]++; cnt2[s[i+5]>>16]++; cnt2[s[i+6]>>16]++; cnt2[s[i+7]>>16]++;
        }
        for (; i < (int)c; i++) cnt2[s[i] >> 16]++;
    }
    { u32 t = 0; for (j = 0; j < NB; j++) { u32 c = cnt2[j]; off[j] = t; pos[j] = 0; t += c; } }
#define P2(X) do { u32 x_ = (X); u32 b_ = x_ >> 16; u32 p_ = pos[b_]; \
    staging[b_ * LINE + p_] = x_; p_++; \
    if (p_ == LINE) { u32 go_ = off[b_]; memcpy(dst + go_, staging + b_ * LINE, 128); off[b_] = go_ + LINE; p_ = 0; } \
    pos[b_] = (u8)p_; } while (0)
    for (j = 0; j < NB; j++) {
        u32 c = cnt1[j];
        if (c == 0) continue;
        u32 *s = src + base1[j];
        int c8 = (int)c & ~7;
        for (i = 0; i < c8; i += 8) {
            P2(s[i]); P2(s[i+1]); P2(s[i+2]); P2(s[i+3]);
            P2(s[i+4]); P2(s[i+5]); P2(s[i+6]); P2(s[i+7]);
        }
        for (; i < (int)c; i++) P2(s[i]);
    }
#undef P2
    for (j = 0; j < NB; j++) { u32 p = pos[j]; if (p > 0) memcpy(dst + off[j], staging + j * LINE, p * 4); }
}

void sort(unsigned *aa, int n) {
    u32 *a = (u32*)aa;
    pass1(a, tmp, n);
    pass2(tmp, a, n);
}

评测结果