代码

// naive 16-bit 2-pass LSD, combined histogram (sol_v16c port to n=1e8)
typedef unsigned int u32;
static u32 tmp[100000000];
static u32 cnt[131072];
void sort(unsigned *aa, int n) {
    u32 *a = (u32*)aa;
    int i;
    for (i = 0; i < 131072; i++) cnt[i] = 0;
    for (i = 0; i < n; i++) { u32 x = a[i];
        cnt[0 + (x & 65535)]++;
        cnt[65536 + ((x>>16) & 65535)]++;
    }
    for (i = 1; i < 65536; i++) cnt[0+i] += cnt[0+i-1];
    for (i = 1; i < 65536; i++) cnt[65536+i] += cnt[65536+i-1];
    for (i = n-1; i >= 0; i--) { u32 x = a[i]; tmp[--cnt[0 + (x & 65535)]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = tmp[i]; a[--cnt[65536 + ((x>>16) & 65535)]] = x; }
}

评测结果