#include <cstdio>
#include <cstdlib>
#include <cstring>
//#include <windows.h>

static int powersof10[] = {1, 10, 100, 1000, 10000,100000,1000000,10000000,100000000,1000000000};

void radix_sort(int* a,int n)
{
	int i,j,num[10],*buckets[10],poz;
	memset(num,0,sizeof(int)*10);
	for(i=0;i<10;i++)
	{
		for(j=0;j<n;j++)
			num[(a[j]/powersof10[i])%10]++;
		for(j=0;j<10;j++)
		{
			buckets[j]=(int *)malloc(sizeof(int)*(num[j]+1));
			buckets[j][0]=num[j];
		}
		for(j=0;j<n;j++)
		{
			buckets[(a[j]/powersof10[i])%10][num[(a[j]/powersof10[i])%10]]=a[j];
			num[(a[j]/powersof10[i])%10]--;
		}
		poz=0;
		for(j=0;j<10;j++)
		{
			for(;buckets[j][0];poz++,buckets[j][0]--)
				a[poz]=buckets[j][buckets[j][0]];
			free(buckets[j]);
		}
	}
}

int comp(const void*a,const void*b)
{
	if(*(int *)a>*(int*)b)
		return 1;
	else
		return 0;
}

inline void display(int *a,int n)
{
	printf("%d",a[0]);
	for(int i=1;i<n;i++)
		printf(" %d",a[i]);
}

void readfile(int a[500000],int &n)
{
	int i;
	FILE *f=fopen("algsort.in","r");
	fscanf(f,"%d\n",&n);
	for(i=0;i<n;i++)
		fscanf(f,"%d ",&a[i]);
	fclose(f);
}

void writefile(int a[500000],int n)
{
	int i;
	FILE *f=fopen("algsort.out","r");
	for(i=0;i<n;i++)
		fprintf(f,"%d ",a[i]);
	fclose(f);
}

void fillrand(int a[500000],int n)
{
	int i;
	for(i=0;i<n;i++)
		a[i]=rand();
}

int main()
{
	unsigned long start;
	int a[500000];
	int n=20;
	readfile(a,n);
	//fillrand(a,n);
	
	//start=GetTickCount();
	radix_sort(a,500000);
	//qsort(a,200000,sizeof(int),comp);
	//printf("Function run time: %lu miliseconds\n",GetTickCount()-start);
	//display(a,10);
	writefile(a,n);
	
	return 0;
}