#include <bits/stdc++.h>

int tmp[500005];

void mergesort(int v[], int left, int right)
{
    if(left < right)
    {
        int m = (left + right) / 2;
        mergesort(v, left, m);
        mergesort(v, m+1, right);
        int i = left, j = m+1, k = 0;
        while(i <= m && j <= right)
        {
            if(v[i] < v[j])
                tmp[k++] = v[i++];
            else
                tmp[k++] = v[j++];
        }
        while(i <= m)
            tmp[k++] = v[i++];
        while(j <= right)
            tmp[k++] = v[j++];
        for(i = left, j = 0; i <= right; i++, j++)
            v[i] = tmp[j];
    }
}

int partition(int v[], int left, int right)
{
    srand(time(NULL));
    int pivot = v[rand() % (right - left) + left], i = left - 1;
    std::cout << "Pivotul este: " << pivot << std::endl;
    std::cout << "Initial vectorul este: ";
    for (int i = left; i <= right; i++)
        std::cout << v[i] << " ";
    std::cout << std::endl;
    i = left - 1;
    int j = right + 1;
    while(true)
    {
        do{i++;}while(v[i] < pivot);
        do{j--;}while(v[j] > pivot);
        if(j <= i) break;
        std::swap(v[i],v[j]);
    }
    std::cout << "La final vectorul este: ";
    for (int i = left; i <= right; i++)
        std::cout << v[i] << " ";
    std::cout << std::endl << std::endl;
    return j;
}

void quicksort(int v[], int left, int right)
{
    if(left >= 0 && right >= 0 && left < right)
    {
        int pi = partition(v, left, right);
        quicksort(v, left, pi);
        quicksort(v, pi+1, right);
    }
}

int main(){
    int v[500005], n;
    std::ifstream f1("algsort.in");
    std::ofstream f2("algsort.out");
    f1 >> n;
    for(int i = 0; i < n; i++)
        f1 >> v[i];
    
    // mergesort(v, 0, n-1);
    quicksort(v, 0, n-1);

    for(int i = 0; i < n; i++)
        f2 << v[i] << " ";
}