代码

// 1001b: sort n = 1<<27. Two chunked 4-pass LSD radix runs + in-place backward merge,
// using a 400MB temp (same footprint as the working 1001 build).
typedef unsigned u32;
static u32 tmpbuf[100000000];
static u32 h0[256], h1[256], h2[256], h3[256];

static void lsd(u32 *a, int n) {
    for (int i = 0; i < 256; i++) { h0[i]=0; h1[i]=0; h2[i]=0; h3[i]=0; }
    for (int i = 0; i < n; i++) { u32 v=a[i]; h0[v&255]++; h1[(v>>8)&255]++; h2[(v>>16)&255]++; h3[v>>24]++; }
    u32 *tmp = tmpbuf;
    u32 s = 0;
    for (int i=0;i<256;i++){ u32 c=h0[i]; h0[i]=s; s+=c; }
    for (int i=0;i<n;i++){ u32 v=a[i]; tmp[h0[v&255]++]=v; }
    s=0; for (int i=0;i<256;i++){ u32 c=h1[i]; h1[i]=s; s+=c; }
    for (int i=0;i<n;i++){ u32 v=tmp[i]; a[h1[(v>>8)&255]++]=v; }
    s=0; for (int i=0;i<256;i++){ u32 c=h2[i]; h2[i]=s; s+=c; }
    for (int i=0;i<n;i++){ u32 v=a[i]; tmp[h2[(v>>16)&255]++]=v; }
    s=0; for (int i=0;i<256;i++){ u32 c=h3[i]; h3[i]=s; s+=c; }
    for (int i=0;i<n;i++){ u32 v=tmp[i]; a[h3[v>>24]++]=v; }
}

void sort(u32 *a, int n) {
    int h = n >> 1;
    lsd(a, h);
    lsd(a + h, n - h);
    u32 *t = tmpbuf;
    int m = n - h;
    for (int i = 0; i < m; i++) t[i] = a[h + i];
    int i = h - 1, j = m - 1, k = n - 1;
    while (j >= 0) {
        if (i >= 0 && a[i] > t[j]) a[k--] = a[i--];
        else a[k--] = t[j--];
    }
}

评测结果