代码

#include <iostream>

#define ceil_div(u, v) (((u) - 1) / (v) + 1)

using namespace std;

static const uint32_t BASE = 4;
static const uint32_t CHUNK_NUM = ceil_div(32, BASE);
static const uint32_t CHUNK_SIZE = 1u << BASE;
static const uint32_t CHUNK_MASK = CHUNK_SIZE - 1;

void sort(unsigned *a, int n) {
    uint32_t cnt[CHUNK_NUM][CHUNK_SIZE] = {};
    for (int i = 0; i < n; ++i)
        for (uint32_t j = 0, k = a[i]; j < CHUNK_NUM; ++j, k >>= BASE)
            ++cnt[j][k & CHUNK_MASK];

    uint32_t *s = new uint32_t[n];
    uint32_t *t = s;
    for (uint32_t i = 0; i < CHUNK_NUM; ++i) {
        for (uint32_t j = 1; j < CHUNK_SIZE; ++j)
            cnt[i][j] += cnt[i][j - 1];
        for (int j = 1; j <= n; ++j) {
            int k = n - j;
            t[--cnt[i][(a[k] >> (BASE * i)) & CHUNK_MASK]] = a[k];
        }
        swap(a, t);
    }
    delete[]s;
}

评测结果