代码

// MSD 11-bit bucket sort + insertion sort inside buckets
static 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 cnt[2048], st[2048], tmp[1<<16];
    for (int i = 0; i < 2048; i++) cnt[i] = 0;
    for (int i = 0; i < n; i++) cnt[a[i] >> 21]++;
    unsigned s = 0;
    for (int i = 0; i < 2048; i++) { unsigned c = cnt[i]; st[i] = s; cnt[i] = s; s += c; }
    for (int i = 0; i < n; i++) { unsigned v = a[i]; tmp[cnt[v >> 21]++] = v; }
    for (int b = 0; b < 2048; b++) {
        int e = (b + 1 < 2048) ? (int)st[b + 1] : n;
        int len = e - (int)st[b];
        if (len > 1) insort(tmp + st[b], len);
    }
    for (int i = 0; i < n; i++) a[i] = tmp[i];
}

评测结果