概念：

归并排序，其实是一种分治和递归算法

将大问题转化为一个个小问题处理，最终整合成一个大问题

模板：

const int N = 2e5 + 5;
int a[N],b[N],n;void mergeSort(int l, int r){if(l>=r) return;int mid=(l+r)>>1; mergeSort(l,mid); mergeSort(mid+1,r);int i=l,j=mid+1,k=l;while(i<=mid&&j<=r){if(a[i]<=a[j])b[k++]=a[i++]; else b[k++]=a[j++];}while(i<=mid)b[k++]=a[i++];while(j<=r)b[k++]=a[j++];for(int i=l;i<=r;i++)a[i]=b[i];
}void solve(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i];mergeSort(1,n);for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
}