#include<iostream>
#include<fstream>
using namespace std;
void mergeArray(int v[], int p, int q, int r)
{
    //build 2 arrays, one for left side and one for right side
    cout<<v[r]<<endl;
    int n1 = q - p + 1, n2 = r - q;
    int Left[n1], Right[n2];
    for(int i = 0; i < n1; i++)
        Left[i] = v[p+i];
    for(int i = 0; i < n2; i++)
        Right[i] = v[q + i + 1];
    //merge these 2 arrays and store the result in an array
    int index1 = 0;
    int index2 = 0;
    int index = p;
    //merge the arrays until one of them ends
    while(index1 < n1 && index2 < n2)
    {
        if(Left[index1] < Right[index2])
        {
            v[index] = Left[index1];
            index1++;
        }
        else
        {
            v[index] = Right[index2];
            index2++;
        }
        index++;
    }
    //check which one has ended and add the remaining elements to its end
    if(index1 == n1)
    {
        while(index2 < n2)
        {
            v[index] = Right[index2];
            index2++;
            index++;
        }
    }
    if(index2 == n2)
    {

        while(index1 < n1)
        {
            v[index] = Left[index1];
            index1++;
            index++;
        }
    }
}//merge method

void mergeSort(int v[], int p, int r)
{
    int q;
    if(p<r)
    {
        q = (p + r) / 2;
        mergeSort(v, p, q);
        mergeSort(v, q+1, r);
        mergeArray(v,p,q,r);
    }
}
int main()
{
    int v[100], n;
    ifstream f("algsort.in");
    ofstream g("algsort.out");
    f>>n;
    for(int i = 0; i < n; i++)
        f>>v[i];
    mergeSort(v,0,n);
    for(int i = 0; i < n; i++)
        g<<v[i]<<"  ";
    f.close();
    g.close();
}