#include <iostream>
#include<time.h>
#include <fstream>
using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");
int n, a[500001],aux[500001];
void quicksort(int a[], int left,int right)
{
    if(left < right)
    {
        int mid = (left+right)/2;
        int pivot = a[mid];
        int poz_left=left, poz_right=right,t=0,nr=0;

        for(int i = left; i <= right; i++)
        {
            if(a[i] < pivot)
                aux[poz_left++] = a[i];
            else {
              if(a[i] > pivot)
                    aux[poz_right--] = a[i];
              else if (a[i] == pivot){
                    if (nr == 0) {t=a[i], nr++;}
                    else aux[poz_left++] = a[i];
                  }
              }

        }
        aux[poz_right] = t;
        for(int i = left; i <= right; i++) a[i]=aux[i];

        quicksort(a,left,poz_left-1);
        quicksort(a,poz_right+1,right);
    }
}
//
// int partition(int v[], int left, int right)
// {
//     int mid = (left + right )/2;
//     int pivot = v[mid],  i = left-1 , j = right + 1;
//     while(true)
//     {
//         do{ i++ ; }while( v[i] < pivot );
//         do{j--;}while( v[j] > pivot );
//         if(i >= j) return j;
//         swap(v[i], v[j]);
//     }
// }
//
// void quicksort(int v[], int left, int right)
// {
//     if(left >= 0 && right >= 0 && left < right)
//     {
//         int i = partition(v, left, right);
//         quicksort(v, left, i);
//         quicksort(v, i+1, right);
//     }
// }

int main() {
  f>>n;
  for (int i=1;i<=n;i++) f >> a[i];

  clock_t start;
  start = clock();

  quicksort(a,1,n);

  clock_t end = clock();
  double time_taken = ((double) (end-start))/CLOCKS_PER_SEC; // in seconds

  cout<< "Quick sort last "<< time_taken<< " seconds " << endl;

  for (int i=1;i<=n;i++)  g << a[i] << " ";
  return 0;
}