代码

#include <algorithm>
#pragma GCC optimize ("O3")
void sort(unsigned* a, int n) {
unsigned x[n];
    unsigned i=0, j=n, k;
    while (i<j) {
        if (a[i]<0x80000000U) {unsigned t = a[i++];
            x[t>>5] |= 1 << (t&31);
        } else {
            std::swap(a[i], a[--j]);
        }
    }
    for (j=0, k=0; k<1<<26; ++k) {
        unsigned c=x[k];
        while (c) {
            unsigned q=__builtin_ctz(c);
            a[j++] = k<<5 | q;
            c &= c-1;
        }
        x[k] = 0;
    }
    for (j=i; j<n; ++j) {
        unsigned t = a[j];
        x[(t>>5)-(1<<26)] |= 1 << (t&31);
    }
    for (j=i, k=0; k<1<<26; ++k) {
        unsigned c=x[k];
        while (c) {
            unsigned q=__builtin_ctz(c);
            a[j++] = k<<5 | q | 0x80000000U;
            c &= c-1;
        }
    }
}

评测结果