代码

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

评测结果