代码

#include <cstring>
static inline void insort(unsigned *p, int len) {
    for (int i = 1; i < len; i++) {
        unsigned v = p[i]; int j = i - 1;
        while (j >= 0 && p[j] > v) { p[j + 1] = p[j]; j--; }
        p[j + 1] = v;
    }
}
void sort(unsigned *a, int n) {
    static unsigned h[4096], st[4096], ne[4096];
    static unsigned tmp[1<<16];
    for (int i = 0; i < 4096; i++) h[i] = 0;
    for (int i = 0; i < n; i++) h[a[i] >> 20]++;
    unsigned s = 0, cnt = 0;
    for (int i = 0; i < 4096; i++) { unsigned c = h[i]; if (c) ne[cnt++] = i; st[i] = s; s += c; h[i] = s; }
    for (int i = n - 1; i >= 0; i--) { unsigned v = a[i]; tmp[--h[v >> 20]] = v; }
    for (unsigned j = 0; j < cnt; j++) {
        unsigned k = ne[j];
        int b = (int)st[k];
        int e = (j + 1 < cnt) ? (int)st[ne[j + 1]] : n;
        if (e - b > 1) insort(tmp + b, e - b);
    }
    memcpy(a, tmp, n * 4);
}

评测结果