代码

#include<algorithm>
#include<cstring>

const int N = 1e8, T = 65536;
unsigned t[N], ct[T];
void sort(unsigned*a, int n) {
    for (int i=0; i<n; i++) ct[a[i]&T-1]++;
    for (int i=1; i<T; i++) ct[i] += ct[i-1];
    for (int i=n-1; ~i; i--) t[--ct[a[i]&T-1]] = a[i];
    memset(ct, 0, T*4);
    for (int i=0; i<n; i++) ct[t[i]>>16&T-1]++;
    for (int i=1; i<T; i++) ct[i] += ct[i-1];
    for (int i=n-1; ~i; i--) a[--ct[t[i]>>16&T-1]] = t[i];
}

评测结果