#include <cstdio>
#include <string>
#include <cstdlib>
#define maxn 1000001
int a[maxn], aux[maxn];
int n;

inline void rad(int n, int byte, int a[], int b[]) 
{
	int count[256], index[256],i;
	memset(count, 0, sizeof(count));
	
	for(i=0;i<n;++i) ++count[(a[i]>>byte)&(255)];
	index[0]=0;
	for(i=1;i<256;++i) index[i]=index[i-1]+count[i-1];
	for(i=0;i<n;++i) b[index[(a[i]>>byte)&(255)]++]=a[i];
}

inline void radix(int n, int a[])
{
	rad(n, 0, a, aux);
	rad(n, 8, 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;
}