代码

typedef unsigned u32;
enum { RAD = 65536, MASK = RAD - 1 };
static u32 temp[200000000];
static u32 low_count[RAD], high_count[RAD];

void sort(u32 *a, int n) {
    for (int i = 0; i < RAD; ++i) low_count[i] = high_count[i] = 0;
    for (int i = 0; i < n; ++i) {
        u32 v = a[i];
        ++low_count[v & MASK];
        ++high_count[v >> 16];
    }
    u32 sl = 0, sh = 0;
    for (int i = 0; i < RAD; ++i) {
        u32 cl = low_count[i], ch = high_count[i];
        low_count[i] = sl; high_count[i] = sh;
        sl += cl; sh += ch;
    }
    for (int i = 0; i < n; ++i) {
        u32 v = a[i]; temp[low_count[v & MASK]++] = v;
    }
    for (int i = 0; i < n; ++i) {
        u32 v = temp[i]; a[high_count[v >> 16]++] = v;
    }
}

评测结果