#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXN 500000
#define LGBUBSORT 10
void readData(int *n, int *v)
{
int i;
scanf("%d",n);
for(i = 1; i <= *n; i++)
scanf("%d",&v[i]);
}
void printVector(int n, int *v)
{
int i;
for(i = 1; i <= n; i++)
printf("%d ",v[i]);
}
void swap(int *x, int *y)
{
int aux = *x;
*x = *y;
*y = aux;
}
void shuffleArray(int n, int *v)
{
int i;
for(i = n; i >= 2; i--)
{
int p = rand()%(i-1) + 1;
swap(&v[p],&v[i]);
}
}
void bubbleSort(int lo, int hi, int *v)
{
int sortat,i;
do
{
sortat = 1;
for(i = lo; i < hi; i++)
if(v[ i ] > v[i + 1])
{
swap(&v[i],&v[i+1]);
sortat = 0;
}
}
while(sortat == 0);
}
int medianOf3(int i, int j, int k, int *v)
{
int a = v[ i ], b = v[ j ], c = v[ k ];
if(b < a)
{
swap(&b,&a);
swap(&i,&j);
}
if(c < a)
{
swap(&c,&a);
swap(&i,&k);
}
if(b > c)
{
swap(&b,&c);
swap(&j,&k);
}
return j;
}
void sort2(int lo, int hi, int *v)
{
if(hi - lo + 1 <= LGBUBSORT)
bubbleSort(lo,hi,v);
else
{
//int p = medianOf3(lo,lo + (hi-lo)/2,hi,v);
int p = lo + rand()%(hi-lo+1);
swap(&v[p],&v[lo]);
int lt = lo, i = lo + 1, gt = hi, ref = v[lo];
while(i <= gt)
{
if(v[ i ] < ref)
{
swap(&v[i],&v[lt]);
i++;
lt++;
}
else
{
if(v[ i ] == ref)
i++;
else
{
swap(&v[ i ], &v[ gt ]);
gt--;
}
}
}
sort2(lo,lt-1,v);
sort2(lt+1,hi,v);
}
}
int main()
{
freopen("algsort.in","r",stdin);
freopen("algsort.out","w",stdout);
int n, v[MAXN+1];
readData(&n,v);
srand(time(NULL));
shuffleArray(n,v);
sort2(1,n,v);
printVector(n,v);
return 0;
}