代码

// 这是 WC 2017 挑战 的 标程
void sort(unsigned *a, int n){
    constexpr int S = 11;
    unsigned _b[100000005], *b;
    unsigned cnt[1<<S];
    int i;
    b = _b;
    for (i = 0; i < 32; i += S) {
        for (int j = 0; j < 1<<S; j++) cnt[j] = 0;
        if (i + S >= 32) {
            for (int j = 0; j < n; j++) ++cnt[a[j] >> i];
            for (int j = 1; j < 1 << S; j++) cnt[j] += cnt[j - 1];
            for (int j = n - 1; j >= 0; j--) b[--cnt[a[j] >> i]] = a[j];
            unsigned *tmp = a;
            a = b, b = tmp;
            continue;
        }
        int t = (1 << S) - 1;
        for (int j = 0; j < n; j++) ++cnt[(a[j] >> i) & t];
        for (int j = 1; j < 1 << S; j++) cnt[j] += cnt[j - 1];
        for (int j = n - 1; j >= 0; j--) b[--cnt[(a[j] >> i) & t]] = a[j];
        unsigned *tmp = a;
        a = b, b = tmp;
    }
    unsigned *tmp = a;
    a = b, b = tmp;
}

评测结果