$O(nlogn)$最大约为$500000*16=8000000=8*10^7$

但是TLE4个点。按这个复杂度似乎是要超，但是归并都这样了，快排还能更低？不解ing

贴个代码：

#include<bits/stdc++.h>
using namespace std;
const int MAX=500000+100;
int n,a[MAX],t[MAX];
void msort(int l,int r)
{
	if(l>=r) return;
	msort(l,(l+r)/2);
	msort((l+r)/2+1,r);
	memset(t,0,sizeof(t));
	int li=l,rj=(l+r)/2+1,nst=l;
	while(li<=(l+r)/2&&rj<=r)
	{
		if(a[li]<=a[rj])
			t[nst]=a[li],li++,nst++;
		else	
			t[nst]=a[rj],rj++,nst++;
	}
	while(li<=(l+r)/2)
		t[nst]=a[li],li++,nst++;
	while(rj<=r)
		t[nst]=a[rj],rj++,nst++;
	for(int i=l;i<=r;i++)
		a[i]=t[i];
}
int main()
{	
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	msort(1,n);
	for(int i=1;i<=n;i++)
		cout<<a[i]<<" ";
	return 0;
}

蒟蒻原本AFO了，回来打个归并……（之前没有打成功过，第一次，请多多指教）