#include <iostream>
#include <vector>
#include<bits/stdc++.h>
# define ll long long 
# define endl "\n"
using namespace std;

//PRINT FUNCTION 
void print(vector<int>b,int n)
 {
    for(int i=0;i<n;i++)
        cout<<"  "<<b[i]<<"  ";
        cout<<endl<<endl;
 }
 
//MERGE FUNCTION

void merge(vector<int>&a,int low ,int high)
{
    int mid=(high+low)/2;
    int i=0,j=0,k=low;
    int p=mid-low+1;
    int q=high-mid;
        vector<int>b(a.size());
    while(i<p and j<q)
    {
        if(a[i+low]<a[mid+j+1])
        {
            b[k++]=a[i+low];
            i++;
        }
        else if(a[i+low]>a[j+mid+1])
        {
            b[k++]=a[j+mid+1];
            j++;
        }
        else{
            b[k++]=a[i+low];
            b[k++]=a[j+mid+1];
            i++;j++;
        }
    }
    while(i<p)
    {
        b[k++]=a[i+low];
        i++;
    }
    while(j<q)
    {
        b[k++]=a[j+mid+1];
        j++;
    }
    for(int i=low;i<=high;i++)
        a[i]=b[i];
}

 //MERGE SORT
 void merge_sort(vector<int>&a,int low,int high)
 {
     if(low>=high)return ;
     int mid=(high+low)/2;           // mid value 
     merge_sort(a,low,mid);         //mergesort for first half
     merge_sort(a,mid+1,high);      //mergersort for second half
     merge(a,low,high);             //merge the two halves
     print(a,a.size());             //print the modified array
 }
 
int main() {
   
    cout<<"ENTER  SIZE  OF AARAY:\n";
    int n;
    cin>>n; //enter size of array
    vector<int>a(n);
    cout<<"ENTER ARRAY ELEMENTS\n";
    
    for(int i=0;i<n;i++)
        cin>>a[i];  //input array
    
    //call the merge_sort function with low=0,high=n-1
    merge_sort(a,0,n-1);
    
    //print the resultant sorted array
    cout<<"\nFINAL ARRAY SORTED IN ASCENDING ORDER:\n";
    print(a,n);
        
          
   
}