For merge sort, we need to do recursive execute first, then merge the left part and the right part, we use two pointers to compare each one of them, then update the sorted elements into a temp array, the extar part of left and right section will be appended to the temp array directly. Then we update the original queue using the temp array.
$time\ O(nlogn)$
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =100010;
int q[N],tmp[N];
int n;
void merge_sort(int l,int r)
{
if(l>=r) return;
int mid=l+r>>1;
merge_sort(l,mid);
merge_sort(mid+1,r);
int i=l,j=mid+1;
int k=0;
while(i<=mid && j<=r)
{
if(q[i]<=q[j]) tmp[k++]=q[i++];
else tmp[k++]=q[j++];
}
while(i<=mid) tmp[k++]=q[i++];
while(j<=r) tmp[k++]=q[j++];
for(i=l,j=0;i<=r;i++,j++) q[i]=tmp[j];
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>q[i];
merge_sort(0,n-1);
for(int i=0;i<n;i++) cout<<q[i]<<" ";
return 0;
}