代码

#include <algorithm>
#include <vector>
using namespace std;

const int B = 1 << 16;
vector<unsigned> cnt[B];

void sort(unsigned *a, int n) {
	--a;
	for(int i = 1; i <= n; ++i)
		cnt[a[i] & ((1 << 16) - 1)].push_back(a[i]);
	for(int i = 0, p = 0; i < (1 << 16); ++i) {
		for(int j = 0; j < cnt[i].size(); ++j)
			a[++p] = cnt[i][j];
		cnt[i].clear();
	}
	
	for(int i = 1; i <= n; ++i)
		cnt[a[i] >> 16].push_back(a[i]);
	for(int i = 0, p = 0; i < (1 << 16); ++i) {
		for(int j = 0; j < cnt[i].size(); ++j)
			a[++p] = cnt[i][j];
		cnt[i].clear();
	}
}

评测结果