#include <fstream>
using namespace std;
int N, *v;
void quickSort(int *arr, int elements) {

  int  piv, *beg, *end, i=0, L, R, swap ;
  beg=new int[N/2+1];
  end=new int[N/2+1];
  beg[0]=0; end[0]=elements;
  while (i>=0) {
    L=beg[i]; R=end[i]-1;
    if (L<R) {
      piv=arr[L];
      while (L<R) {
        while (arr[R]>=piv && L<R) R--; if (L<R) arr[L++]=arr[R];
        while (arr[L]<=piv && L<R) L++; if (L<R) arr[R--]=arr[L]; }
      arr[L]=piv; beg[i+1]=L+1; end[i+1]=end[i]; end[i++]=L;
      if (end[i]-beg[i]>end[i-1]-beg[i-1]) {
        swap=beg[i]; beg[i]=beg[i-1]; beg[i-1]=swap;
        swap=end[i]; end[i]=end[i-1]; end[i-1]=swap; }}
    else {
      i--; }}
      delete[] beg; delete[] end;
  }
  int main()
  {
	  ifstream in("algsort.in");
	  in>>N;
	  v=new int[N];
	  for( int i=0; i < N; ++i ) in>>v[i];
	  quickSort( v, N );
	  ofstream out("algsort.out");
	  for( int i=0; i < N; ++i ) out<<v[i]<<' ';
	  delete[] v;
	  return 0;
	 }