MERGE_SORT

#include<bits/stdc++.h>
using namespace std;

void Merge(int A[],int p,int q, int r){
    int i,j,k;
    int n1= q-p+1;
    int n2= r-q;
    int L[n1+1];int R[n2+1];
    for(i=1;i<=n1;i++){
        L[i]=A[p+i-1];
    }
    for(j=1;j<=n1;j++){
        R[i]=A[q+j];
    }
    L[n1+1]=999999;
    R[n2+1]=999999;
    i=1;j=1;
    for(k=p;k<=r;k++){
        if(L[i]<=R[j]){
            A[k]=L[i];
            i++;
        }
        else{
            A[k]=R[j];
            j++;
        }
    }

}

void MergeSort(int A[],int p, int r){
    int q;
    if(p<r){
        q=(p+r)/2;
        MergeSort(A,p,q);
        MergeSort(A,q+1,r);
        Merge(A,p,q,r);
    }
}

int main()
{

      int n,p,r,i;
    cin>>n;
    int A[n];
    for(i=0;i<n;i++)
    {
        cin>>A[i];
    }
    p=0;
    r=n-1;
    MergeSort(A,p,r);
    for(i=0;i<n;i++)
    {
        cout<<A[i]<<" ";
    }
    return 0;
}