归并

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005];

void merge(int l,int mid,int r){
	int leftStart = l,leftEnd=mid;
	int rightStart=mid+1,rightEnd=r;
	int p=l;
	
	while(leftStart<=leftEnd&&rightStart<=rightEnd){
		if(a[leftStart]<=a[rightStart]){
			b[p++]=a[leftStart++];
		}else{
			b[p++]=a[rightStart++];
		}
	}
	while(leftStart<=leftEnd) b[p++]=a[leftStart++];
	while(rightStart<=rightEnd) b[p++]=a[rightStart++];
	
	for(int i=l;i<=r;i++){
		a[i]=b[i];
	}
}

void msort(int l,int r){
	if(l<r){
		int mid=(l+r)/2;
		msort(l,mid);
		msort(mid+1,r);
		merge(l,mid,r);
	}
	
}
int main(){
	int n;
	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;
}