#include <fstream>

bool comp(int a,int b)
{
    return a<b;
}

void Merge(int v[],int left,int right,bool(*comp)(int,int)=comp)
{
    int k=0,mid=(left+right)/2;
    int *aux=new int[right-left+1];
    int i=left,j=mid+1;
    while(i<=mid && j<=right)
    {
        if(comp(v[i],v[j]))
        {
            aux[k]=v[i];// aux[k++]=v[i]
            i++;
            k++;
        }
        else{
            aux[k]=v[j];
            j++;
            k++;
        }
    }
    while(i<=mid)
    {
        aux[k]=v[i];
        i++;
        k++;
    }
    while(j<=right)
    {
        aux[k]=v[j];
        j++;
        k++;
    }
    for(int i=0;i<k;i++)
        v[left+i]=aux[i];
    delete aux; // se elibereaza memoria
}

void mergeSort(int v[],int left,int right,bool(*comp)(int,int)=comp)
{
    if(left<right)
    {
        int mid=(left+right)/2;
        mergeSort(v,left,mid,comp);
        mergeSort(v,mid+1,right,comp);
        Merge(v,left,right,comp);
    }
}

int main()
{
    int n;
    std::ifstream in("algsort.in");//in fstream(pt Maria noob, std e o clasa) 
    in>>n;
    int *v=new int[n];
    for(int i=0;i<n;i++)
    {
        in>>v[i];
    }
    mergeSort(v,0,n-1);
    std::ofstream out("algsort.out");//out fstream
    for(int i=0;i<n;i++)
    {
        out<<v[i]<<' ';
    }
    return 0;
}