#include <cstdio>
#include <string>
#include <cstdlib>
#define maxn 1000001
int a[maxn], aux[maxn];
int n;
const int T =(1<<16);
inline void rad(int n, int byte, int a[], int b[]) 
{
	int count[T], index[T],i;
	memset(count, 0, sizeof(count));
	
	for(i=0;i<n;++i) ++count[(a[i]>>byte)&(T-1)];
	index[0]=0;
	for(i=1;i<T;++i) index[i]=index[i-1]+count[i-1];
	for(i=0;i<n;++i) b[index[(a[i]>>byte)&(T-1)]++]=a[i];
}

inline void radix(int n, int a[])
{
	rad(n, 0, a, aux);
	rad(n, 16, aux, a);
//	rad(n, 16, a, aux);
	//rad(n, 24, aux, a);
}

int main()
{
	int i;
	n=1000000;
	srand(time(0));
	for(i=0;i<n;++i)a[i]=rand()%123456672;
	//for(i=0;i<n;++i) printf("%d ", a[i]);
	printf("\n");
	
	
	radix(n, a);
	
	//for(i=0;i<n;++i) printf("%d ", a[i]);
	return 0;
}