#include <iostream>
#include <fstream>
#include <algorithm>
#include <time.h>

using namespace std;

int partitie( int *v, int st, int dr)
{
    int p = v[dr], i, j, aux;

    i = st-1;
    for ( j = st; j < dr ; j++)
    {
        if ( v[j] <= p )
        {
            i++;
            swap ( v[i], v[j]);
        }
    }
    swap (v[i+1],v[dr]);

    return (i+1);
}

void quickSort ( int *v, int st, int dr)
{
    if( st >= dr)
        return;

    int p = partitie ( v, st ,dr);
    quickSort(v, st, p-1);
    quickSort(v, p+1, dr);
}

int pivot (int *v, int st, int dr)
{
    int x1 ,x2, x3 ,y = dr - st + 1 ;

    x1 = rand() % y + st;
    x2 = rand() % y + st;
    x3 = rand() % y + st;

    if(v[x1] <= v[x2] && v[x1] <= v[x3])
    {
        if( v[x2] <= v[x3])
            return v[x2];
        return v[x3];
    }
    if(v[x2] <= v[x1] && v[x2] <= v[x3])
    {
        if( v[x3] <= v[x1])
            return v[x3];
        return v[x1];
    }

    if(v[x3] <= v[x1] && v[x3] <= v[x2])
    {
        if( v[x2] <= v[x1])
            return v[x2];
        return v[x1];
    }
}

void QuickSort ( int *v ,int st, int dr)
{
    if ( st >= dr )
        return;
    int p = pivot (v, st, dr);
    int i = st , j = dr;
    while ( i <=j)
    {
        while ( v[i] < p )
            i++;
        while ( v[j] > p)
            j--;
        if( i<= j)
        {
            swap(v[i], v[j]);
            i++;
            j--;
        }
    }

    QuickSort(v, st ,j);
    QuickSort (v, i, dr);
}

int main()
{
    int n, *v, i;

    ifstream in("algsort.in");
    ofstream out ("algsort.out");

    in >> n;
    v = new int [n+1];
    for (i = 0 ; i < n ; i++)
        in >> v[i];

    QuickSort (v, 0, n-1);

    for (i = 0; i < n; i++)
        out << v[i] << " ";

    in.close();
    out.close();

    return 0;
}