代码

// 1001b: 4-pass 8-bit LSD radix, combined histogram, 512MB buffer.
typedef unsigned int u32;
static u32 tmp[1 << 27];
static u32 cnt[1024];

void sort(unsigned *a, int n) {
    u32 *p = (u32*)a;
    u32 *c0 = cnt, *c1 = cnt+256, *c2 = cnt+512, *c3 = cnt+768;
    int i;
    for (i = 0; i < 1024; i++) cnt[i] = 0;
    for (i = 0; i < n; i++) { u32 x = p[i]; c0[x & 255]++; c1[(x>>8)&255]++; c2[(x>>16)&255]++; c3[x>>24]++; }
    for (i = 1; i < 256; i++) { c0[i]+=c0[i-1]; c1[i]+=c1[i-1]; c2[i]+=c2[i-1]; c3[i]+=c3[i-1]; }
    for (i = n-1; i >= 0; i--) { u32 x = p[i]; tmp[--c0[x & 255]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = tmp[i]; p[--c1[(x>>8)&255]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = p[i]; tmp[--c2[(x>>16)&255]] = x; }
    for (i = n-1; i >= 0; i--) { u32 x = tmp[i]; p[--c3[x>>24]] = x; }
}

评测结果