#include <iostream>
#include<stdlib.h>
#include<fstream>
using namespace std;


void prt_arr(int*a,int len)
{
    ofstream out("algsort.out");
    for(int i=0; i<len; i++)
        out<<a[i]<<" ";

}

void merge(int*a,int l,int r)
{
    int size=r-l+1;
    int middle=(l+r)/2;
    int aux[size];

    int index=0,p=l,q=middle+1;

    while(p<=middle && q<=r)
    {
        if(a[p]<a[q])
        {
            aux[index]=a[p];
            p++;
        }
        else
        {
            aux[index]=a[q];
            q++;
        }
        index++;
    }





    if(q>r)
    {
        for(int i=p; i<=middle; i++)
        {
            aux[index]=a[i];
            index++;
        }


    }

    else
    {
        for(int i=q; i<=r; i++)
        {
            aux[index]=a[i];
            index++;
        }

    }


    for(int i=0; i<size; i++)
        a[l+i]=aux[i];

}



void merge_sort(int*a,int l,int r)
{
    if(l>=r)
        return;

    int middle=(l+r)/2;
    merge_sort(a,l,middle);
    merge_sort(a,middle+1,r);

    merge(a,l,r);




}

bool is_sorted(int*a,int len)
{

    for(int i=0; i<len-1; i++)
    {
        if(a[i]>a[i+1])
        {
            return false;
        }
    }
    return true;

}




int main()
{
    ifstream in("algsort.in");
    int a[500000];
    int n;
    in>>n;
    for(int i=0; i<n; i++)
        in>>a[i];

    merge_sort(a,0,n-1);


    return 0;
}