代码

#include <algorithm>

const int N  = 1e8 + 100, B = 1 << 16;
unsigned b[N];
unsigned cnt[B], *p[B], *pp;
void sort(unsigned *a, int n) {
	for(int i = 1; i <= n; ++i)
		++cnt[a[i] & (B - 1)];
	pp = b + 1;
	for(int i = 0; i < B; ++i)
		p[i] = pp, pp += cnt[i], cnt[i] = 0;
	for(int i = 1; i <= n; ++i)
		*p[a[i] & (B - 1)]++ = a[i];
	
	for(int i = 1; i <= n; ++i)
		++cnt[b[i] >> 16];
	pp = a + 1;
	for(int i = 0; i < B; ++i)
		p[i] = pp, pp += cnt[i], cnt[i] = 0;
	for(int i = 1; i <= n; ++i)
		*p[b[i] >> 16]++ = b[i];
}

评测结果