#include<iostream>
using namespace std;
int mid,i,j,k;
int b[20];
void merge(int arr[], int lb, int mid, int ub){
i=lb;
j=mid+1;
k=lb;
while(i<=mid && j<=ub){
if(arr[i]<arr[j]){
b[k]=arr[i];
i++;
}
else{
b[k]=arr[j];
j++;
}
k++;
}
if(i>mid){
while(j<=ub){
b[k]=arr[j];
j++;
k++;
}
}
else{
while(i<=mid){
b[k]=arr[i];
i++;
k++;
}
}
for(k=0; k<=ub; k++){
arr[k]=b[k];
}
}
void mergesort(int arr[],int lb, int ub){
if(lb<ub){
mid=(lb+ub)/2;
mergesort(arr,lb,mid);
mergesort(arr,mid+1,ub);
merge(arr,lb,mid,ub);
}
}
int main(){
int n,temp,i,j;
cout<<"Enter the array size"<<endl;
cin>>n;
int arr[n];
cout<<"Enter the elements"<<endl;
for(i=0; i<n; i++){
cin>>arr[i];
}
mergesort(arr,0,n-1);
cout<<"Sorted array is";
for(i=0; i<n; i++){
cout<<arr[i]<<" ";
}
return 0;
}