#include <fstream>
#include <cstdlib>
#include <ctime>
#define SIZE 500000
#define RANDOM(a, b) ((rand() % (b-a+1)) + a)
using namespace std;


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

int A[SIZE], N;

void swap(int n1, int n2)
{
    int aux = A[n1];
    A[n1] = A[n2];
    A[n2] = aux;
}

void insertion_sort(int left, int right)
{
    for (int i = left+1; i <= right; ++i)
    {
        int e = A[i];
        int j = i - 1;
        while (j >= left && A[j] > e)
        {
            if (A[j] > e)
            {
                A[j+1] = A[j];
            }
            
            --j;
        }
        
        A[j+1] = e;
    }
}

int random_partition(int left, int right)
{
    int r = RANDOM(left, right);
    swap(left, r);
    
    int x = A[left];
    
    int i = left - 1;
    int j = right + 1;
    
    while (true)
    {
        do 
        {
            ++i;
        } while (A[i] < x);
        
        do
        {
            --j;
        } while (A[j] > x);
        
        
        if (i < j)
        {
            swap(i, j);
        }
        else
        {
            return j;
        }
    }
}

void random_quicksort(int left, int right)
{
    if (left < right)
    {
        if ((right - left) <= 40)
        {
            insertion_sort(left, right);
        }
        else
        {
            int pivot = random_partition(left, right);
            random_quicksort(left, pivot);
            random_quicksort(pivot+1, right);
        }
    }
}

int main()
{
    ifs >> N;
    for (int i = 0; i < N; ++i)
    {
        ifs >> A[i];
    }
    
    // Init random seed
    srand(time(NULL));
    
    random_quicksort(0, N-1);
    
    for (int i = 0; i < N; ++i)
    {
        ofs << A[i] << " ";
    }

    return 0;
}