代码

#include <algorithm>

#pragma GCC optimize("3,inline,Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
const int ful = (1 << 16) - 1;
int t0[ful + 1], t1[ful + 1];
unsigned *b = new unsigned[100000000];
void sort(unsigned *a, int n) {
    unsigned i;
    for (i = 0; i < n;) {
        ++t0[a[i] & ful], ++t1[(a[i] >> 16) & ful], ++i;
        ++t0[a[i] & ful], ++t1[(a[i] >> 16) & ful], ++i;
        ++t0[a[i] & ful], ++t1[(a[i] >> 16) & ful], ++i;
        ++t0[a[i] & ful], ++t1[(a[i] >> 16) & ful], ++i;
    }
    t0[1] += t0[0], t1[1] += t1[0];
    t0[2] += t0[1], t1[1] += t1[1];
    t0[3] += t0[2], t1[1] += t1[2];
    for (i = 4; i < n;) {
        t0[i] += t0[i - 1], t1[i] += t1[i - 1], ++i;
        t0[i] += t0[i - 1], t1[i] += t1[i - 1], ++i;
        t0[i] += t0[i - 1], t1[i] += t1[i - 1], ++i;
        t0[i] += t0[i - 1], t1[i] += t1[i - 1], ++i;
    }
    for (i = n; i > 3;) {
        b[--t0[a[i] & ful]] = a[i], --i;
        b[--t0[a[i] & ful]] = a[i], --i;
        b[--t0[a[i] & ful]] = a[i], --i;
        b[--t0[a[i] & ful]] = a[i], --i;
    }
    b[--t0[a[i] & ful]] = a[i], --i;
    b[--t0[a[i] & ful]] = a[i], --i;
    b[--t0[a[i] & ful]] = a[i], --i;
    b[--t0[a[i] & ful]] = a[i], --i;
    
    for (i = n; i > 3;) {
        a[--t1[(a[i] >> 16) & ful]] = b[i], --i;
        a[--t1[(a[i] >> 16) & ful]] = b[i], --i;
        a[--t1[(a[i] >> 16) & ful]] = b[i], --i;
        a[--t1[(a[i] >> 16) & ful]] = b[i], --i;
    }
    a[--t1[(a[i] >> 16) & ful]] = b[i], --i;
    a[--t1[(a[i] >> 16) & ful]] = b[i], --i;
    a[--t1[(a[i] >> 16) & ful]] = b[i], --i;
    a[--t1[(a[i] >> 16) & ful]] = b[i], --i;
}

评测结果