代码

void sort(unsigned* a, int n) {
    constexpr int BASE_WIDTH = 8;
    constexpr unsigned BASE = 1 << BASE_WIDTH;

    auto cursors = std::array<std::array<int, BASE>, 4>();
    for (int i = 0; i < n; i++) {
        cursors[0][a[i] & (BASE - 1)]++;
        cursors[1][(a[i] >> BASE_WIDTH) & (BASE - 1)]++;
        cursors[2][(a[i] >> (2 * BASE_WIDTH)) & (BASE - 1)]++;
        cursors[3][a[i] >> (3 * BASE_WIDTH)]++;
    }

    for (int iter = 0; iter < 4; iter++) {
        int prefix_offset = 0;
        for (unsigned v = 0; v < BASE; v++) {
            std::swap(prefix_offset, cursors[iter][v]);
            prefix_offset += cursors[iter][v];
        }
    }

    auto buffer = new unsigned[n];

    for (int i = 0; i < n; i++) {
        buffer[cursors[0][a[i] & (BASE - 1)]++] = a[i];
    }
    for (int i = 0; i < n; i++) {
        a[cursors[1][(buffer[i] >> BASE_WIDTH) & (BASE - 1)]++] = buffer[i];
    }
    for (int i = 0; i < n; i++) {
        buffer[cursors[2][(a[i] >> (2 * BASE_WIDTH)) & (BASE - 1)]++] = a[i];
    }
    for (int i = 0; i < n; i++) {
        a[cursors[3][buffer[i] >> (3 * BASE_WIDTH)]++] = buffer[i];
    }

    delete[] buffer;
}

评测结果