代码

#include <cstring>

void sort(unsigned *a, int n) {
	const unsigned U = 1 << 16, All = U - 1;
	unsigned cnt[1 << 16];
	unsigned *b = new unsigned[n];
	memset(cnt, 0, 1 << 18);
	for (int i = 0; i < n; ++i) ++cnt[a[i] & All];
	for (int i = 1; i < All; ++i) cnt[i] += cnt[i - 1];
	for (int i = n - 1; ~i; --i) b[--cnt[a[i] & All]] = a[i];
	memset(cnt, 0, 1 << 18);
	for (int i = 0; i < n; ++i) ++cnt[b[i] >> 16];
	for (int i = 1; i < All; ++i) cnt[i] += cnt[i - 1];
	for (int i = n - 1; ~i; --i) a[--cnt[b[i] >> 16]] = b[i];
	delete[] b;
}

评测结果