代码

unsigned _b[50000005];

void sort(unsigned *a, int n) {
    const int S = 4;
    unsigned *b;
    unsigned cnt[256];
    int i;
    b = _b;
    for (i = 0; i < 32; i += S) {
        for (int j = 0; j < 1 << S; j++) cnt[j] = 0;
        if (i + S >= 32) {
            for (int j = 0; j < n; j++) ++cnt[a[j] >> i];
            for (int j = 1; j < 1 << S; j++) cnt[j] += cnt[j - 1];
            for (int j = n - 1; j >= 0; j--) b[--cnt[a[j] >> i]] = a[j];
            unsigned *tmp = a;
            a = b, b = tmp;
            continue;
        }
        int t = (1 << S) - 1;
        for (int j = 0; j < n; j++) ++cnt[(a[j] >> i) & t];
        for (int j = 1; j < 1 << S; j++) cnt[j] += cnt[j - 1];
        for (int j = n - 1; j >= 0; j--) b[--cnt[(a[j] >> i) & t]] = a[j];
        unsigned *tmp = a;
        a = b, b = tmp;
    }
}

#include <algorithm>
#define N 50000000

unsigned _a[N + 5];
int main() {
 for (int i = 0; i < N; i++) {
  _a[i] = i * 123456789;
 }
 sort(_a, N);
}

评测结果