#include<iostream>
using namespace std;

void SubMerge(int a[],int l,int mid,int r);

void Merge(int a[],int l,int mid1,int mid2,int r)
{
    SubMerge(a,l,mid1,mid2);
    SubMerge(a,l,mid2,r);
}

void SubMerge(int a[],int l,int mid,int r)
{
    int n1=(mid-l)+1,left[n1];
    int n2=(r-(mid+1))+1,right[n2];

    int i,j,k;
    for (i=0, k=l; i<n1; i++, k++)
        left[i]=a[k];

    for (i=0, k=mid+1; i<n2; i++, k++)
        right[i]=a[k];

    i=0,j=0,k=l;
    while(i<n1 && j<n2)
    {
        if(left[i]<right[j])
            a[k]=left[i],i++;
        else
            a[k]=right[j],j++;
        k++;
    }

    while(i<n1)
        a[k]=left[i],i++,k++;

    while(j<n2)
        a[k]=right[j],j++,k++;
}




void MergeSort(int a[],int l,int r)
{
    if (l<r)
    {
        int temp=(r-l)/3;

        int mid1=l+temp;
        int mid2=l+temp*2;

        MergeSort(a,l,mid1);
        MergeSort(a,mid1+1,mid2);
        MergeSort(a,mid2+1,r);

        Merge(a,l,mid1,mid2,r);
    }
}


void display(int a[],int n)
{
    for (int i=0; i<n; i++)
        cout<<a[i]<<" ";
    cout<<endl;
}


int main()
{
    int n;
    cout<<"ENTRE THE SIZE : ";
    cin>>n;

    int a[n];
    cout<<"Enter Data : ";
    for(int i=0; i<n; i++)
        cin>>a[i];

    int l=0,r=n-1;

    cout<<"Unsorted Array : ";
    display(a,n);

    MergeSort(a,l,r);

    cout<<"Sorted Array : ";
    display(a,n);
}