代码

#include <algorithm>
#include <array>
#include <vector>

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

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

    for (int iter = 0; iter < 2; 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]++] = buffer[i];
    }

    delete[] buffer;
}

评测结果