归并排序的时间复杂度是 $O(n\log n)$ 的，和快速排序一样，而且不会退化

但是不吸氧会 T 掉 $4$ 个点

常数真的有这么大吗/oh

#include<bits/stdc++.h>
using namespace std;
int a[100010],b[100010],n;
void mgs(int l,int r) {
	if(l==r)
		return;
	int mid=l+r>>1;
	mgs(l,mid);
	mgs(mid+1,r);
	int p1=l,p2=mid+1,p3=l;
	while(p1<=mid&&p2<=r) {
		if(a[p1]<a[p2])b[p3++]=a[p1++];
		else b[p3++]=a[p2++];
	}
	while(p1<=mid)b[p3++]=a[p1++];
	while(p2<=r)b[p3++]=a[p2++];
	for(int i=1; i<=r; i++)a[i]=b[i];
}
int main() {
	cin>>n;
	for(int i=1; i<=n; i++)cin>>a[i];
	mgs(1,n);
	for(int i=1; i<=n; i++)cout<<a[i]<<" ";
	return 0;
}