代码

#include <algorithm>

const int ful = (1 << 16) - 1;
int t0[ful + 1], t1[ful + 1];
unsigned *b = new unsigned[100000000];
void sort(unsigned *a, int n) {
    int 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;
    }
    for (i = 1; i <= ful; ++i) {
        t0[i] += t0[i - 1], t1[i] += t1[i - 1];
    }
    for (i = n - 1; i >= 0;) {
        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 - 1; i >= 0;) {
        a[--t1[(b[i] >> 16) & ful]] = b[i], --i;
        a[--t1[(b[i] >> 16) & ful]] = b[i], --i;
        a[--t1[(b[i] >> 16) & ful]] = b[i], --i;
        a[--t1[(b[i] >> 16) & ful]] = b[i], --i;
    }
}

评测结果