↑题面↑

然后我写了归并但是……在多次测试之后MLE了（悲）

#include<bits/stdc++.h>
using namespace std;
int n,k[1000010],temp[1000010];

void MergeMain(int l1,int r1,int l2,int r2){
	int l1_s = l1,i = 1;
	while(l1 <= r1 && l2 <= r2){
		if(k[l1] >= k[l2]) temp[i++] = k[l1++];
		else temp[i++] = k[l2++];
	}
	while(l1 <= r1) temp[i++] = k[l1++];
	while(l2 <= r2) temp[i++] = k[l2++];
	for(int ii = l1_s;ii <= r2;ii++) k[ii] = temp[ii - l1_s + 1];
	return;
}

void MergeSort(int l,int r){
	if(l == r) return;
	MergeSort(l,(l + r) >> 2);
	MergeSort((l + r) >> 2 + 1,r);
	MergeMain(l,(l + r) >> 2,(l + r) >> 2 + 1,r);
	return;
}

int main(){
	scanf("%d",&n);
	for(int i = 1;i <= n;i++) scanf("%d",&k[i]);
	MergeSort(1,n);
	for(int i = 1;i <= n;i++) printf("%d\n",k[i]);
	return 0;
}

求神犇助~