代码

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

typedef unsigned u32;
typedef unsigned long long u64;

enum { BITMAP_WORDS = 1U << 26 };
static u64 bitmap[BITMAP_WORDS] __attribute__((aligned(2097152)));

void sort(u32 *a, int n) {
    int i = 0;
    for (; i + 32 < n; ++i) {
        u32 future = a[i + 32];
        __builtin_prefetch(bitmap + (future >> 6), 1, 0);
        u32 value = a[i];
        bitmap[value >> 6] |= 1ULL << (value & 63U);
    }
    for (; i < n; ++i) {
        u32 value = a[i];
        bitmap[value >> 6] |= 1ULL << (value & 63U);
    }

    u32 output = 0;
    for (u32 word_index = 0; word_index < BITMAP_WORDS; ++word_index) {
        u64 word = bitmap[word_index];
        while (word) {
            a[output++] = (word_index << 6) | (u32)__builtin_ctzll(word);
            word &= word - 1;
        }
    }
}

评测结果