代码

const unsigned int m=16,M=65535;
unsigned int b[100000010],cnt[66666],cnt2[66666];
//最后一次，这次应该不会超内存吧。。 
void sort(unsigned *a, int n)
{
	int i;
	for(i=0;i<n;++i) ++cnt[a[i]&M];
	for(i=1;i<=M;++i) cnt[i]+=cnt[i-1];
	for(i=n;i--;) b[--cnt[a[i]&M]]=a[i];
	for(i=0;i<n;++i) ++cnt2[b[i]>>m]; 
	for(i=1;i<=M;++i) cnt2[i]+=cnt2[i-1];
	for(i=n;i--;) a[--cnt2[b[i]>>m]]=b[i];
}

评测结果