#include <iostream>
using namespace std;
void merge(vector<int>&n,int low,int mid,int high){
vector<int>temp;
int left=low;
int right=mid+1;
while(left<=mid && right<=high){
if(arr[left]<=arr[right]){
temp.push_back(arr[left]);
left++;
}else{
temp.push_Back(arr[right]);
right++;
}
while(left<=mid){
temp.push_back(arr[left]);
left++;
}
while(right<=high){
temp.push_back(arr[right]);
right++;
}
for(int i=low;i<=high;i++){
arr[i]=temp[i-low]
}
}
}
int main() {
void ms(vector<int>&arr,int low,int high){
if(low==high)return;
int mid=(low+high)/2;
ms(arr,low,mid);
ms(arr,mid+1,high);
merge(arr,low,mid,high);
}
void MergeSort(vector<int>&arr,int n){
ms(arr,0,n-1);
}
return 0;
}