#include<iostream>
#include<vector>
using namespace std;
void merge(vector<int> &a,int l,int mid,int r){
	vector<int> b;
	int i=l,j=mid+1;
	while(i<=mid && j<=r){
		if(a[i]<a[j]){
			b.push_back(a[i]);
			++i;
		} else{
			b.push_back(a[j]);
			++j;
		}
	}
	while(i<=mid){
		b.push_back(a[i]);
		++i;
	}
	while(j<=r){
		b.push_back(a[j]);
		++j;
	}
	for(int i=l;i<=r;++i){
		a[i]=b[i-l];
	}
}
void mergesort(vector<int> &a,int l,int r){
	//sort:[a+l,a+r]
	if(l==r)	return;
	else if(l+1==r){
		if(a[l]>a[r])	swap(a[l],a[r]);
		return;
	} else{
		int tmp=1,nowi=l;
		while(nowi<=r){
			if(r-nowi<(tmp>>1)+1){
				mergesort(a,nowi,r);
				merge(a,l,nowi-1,r);
				return;
			}
			mergesort(a,nowi,nowi+(tmp>>1));
			merge(a,l,max(l,nowi-1),nowi+(tmp>>1));
			nowi+=(tmp>>1)+1;
			tmp<<=1;
		}
	}
}
int main(){
	vector<int> a;
	int n,m;
	cin >> n;
	a.push_back(0);
	for(int i=1;i<=n;i++){
		int p;
		cin >> p;
		a.push_back(p);
	} 
	mergesort(a,1,n);
	for(int i=1,len=a.size();i<len;i++){
		cout << a[i] << ' ';
	}
	return 0;
}

函数mergesort在r-l+1，也就是排序的长度为n的时候，时间复杂度是多少，常数大不大（与归并排序、快速排序等比较）