代码

#include<cstring>
#define N 100000001
void sort(unsigned *a, int n)
{
	unsigned b[N];
	unsigned nxt[N];
	unsigned h[65537];
	memset(h,0,sizeof(h));
	register unsigned p=0;
	for(register unsigned i=0;i<n;i++){register unsigned ii=a[i]&65535;++p;nxt[p]=h[ii];b[p]=a[i];h[ii]=p;}
	for(register unsigned i=0,c=0;i<65536;i++){for(register signed k=h[i];k;k=nxt[k])a[++c]=b[k];}
	
	memset(h,0,sizeof(h));
	p=0;
	for(register unsigned i=0;i<n;i++){register unsigned ii=(a[i]>>16)&65535;++p;nxt[p]=h[ii];b[p]=a[i];h[ii]=p;}
	for(register unsigned i=0,c=0;i<65536;i++){for(register signed k=h[i];k;k=nxt[k])a[++c]=b[k];}
	
}

评测结果