/*

Quick Sort- varianta din CLR + pivot random

*/
using namespace std;
#include<iostream>
#include<fstream>
#include<cstdlib>
#define nmax 500010
ofstream fout("algsort.out");
int N,a[nmax];
int select(int l,int r)
{
    int i,j;

    int popiv;
    popiv=rand()%(r-l+1)+l;
    swap(a[l],a[popiv]);

    int pivot;
    pivot=a[l];
    i=l-1;
    j=r+1;
    while(i<j)
    {
        do
        {
            i++;
        }while(a[i]<pivot);
        do
        {
            j--;
        }while(a[j]>pivot);
        if(i<j)
        {
            swap(a[i],a[j]);
        }


    }

 return j;
}

void qsort(int l,int r)
{
    if(l==r) return;
    int p=select(l,r);

    qsort(l,p);
    qsort(p+1,r);

}

void cit()
{
    ifstream fin("algsort.in");
    fin>>N;
    int i;
    for(i=1;i<=N;i++)
    {

        fin>>a[i];
    }

    fin.close();

}

int main()
{
    srand(time(0));
    cit();

    qsort(1,N);
    int i;
    for(i=1;i<=N;i++)
    {

        fout<<a[i]<<" ";
    }
    fout.close();
    return 0;
}