代码

#pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")

#define BITMAP_WORDS (1U << 27)
static unsigned bitmap[BITMAP_WORDS] __attribute__((aligned(2097152)));

void sort(unsigned *a, int n) {
    for (int i = 0; i < n; ++i) {
#ifdef BITMAP_PREFETCH
        if (i + BITMAP_PREFETCH < n)
            __builtin_prefetch(bitmap + (a[i + BITMAP_PREFETCH] >> 5), 1, 0);
#endif
        unsigned value = a[i];
        bitmap[value >> 5] |= 1U << (value & 31);
    }
    unsigned output = 0;
    for (unsigned word_index = 0; word_index < BITMAP_WORDS; ++word_index) {
        unsigned bits = bitmap[word_index];
        while (bits) {
            a[output++] = (word_index << 5) + (unsigned)__builtin_ctz(bits);
            bits &= bits - 1;
        }
    }
}

评测结果