#include<stdio.h>

void merge(int a[],int b[],int low,int mid,int high){
    int h = low;
    int j = mid+1;
    int i = low;
    while(h<=mid && j<=high){
        if(a[h]<=a[j]){
            b[i] = a[h];
            h += 1;
        }
        else{
            b[i] = a[j];
            j += 1;
        }
        i += 1;
    }
    if(h>mid){
        for(int k=j;k<=high;k++){
            b[i] = a[k];
            i += 1;
        }
    }
    else{
        for(int k=h;k<=mid;k++){
            b[i] = a[k];
            i += 1;
        }
    }
    for(int k=low;k<=high;k++){
        a[k] = b[k];
    }
}

void mergeSort(int a[],int b[] , int low,int high){
    if(low<high){
        int mid = (low+high)/2;
        mergeSort(a,b,low,mid);
        mergeSort(a,b,mid+1,high);
        merge(a,b,low,mid,high);
    }
}

int main(){
    int n;
    printf("\n Enter size:");
    scanf("%d",&n);
    int a[n],b[n];
    printf("\n Enter elements:");
    for(int i = 0 ;i<n;i++){
        scanf("%d",&a[i]);
    }
    mergeSort(a,b,0,n-1);
    printf("\n Sorted Elements:");
    for(int i=0;i<n;i++){
        printf("%d \t",a[i]);
    }
    printf("\n");
    return 0;
}