归并排序

//归并排序 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int n,a[N],b[N];
void h(int l1,int r1,int l2,int r2){//归操作 
//l1是第一部分的左指针 r1是第一部分的右指针
//l2是第二部分的左指针 r2是第二部分的右指针
	int t=1; //t为头指针 
	int x1=l1,x2=l2; //将l1给x1 l2给x2 
	while(x1<=r1&&x2<=r2){
		//谁小就将他给b[] 
		if(a[x1]<=a[x2]){
			b[t++]=a[x1++];
		}
		else{
			b[t++]=a[x2++];
		}
	}
	//有可能有剩余，就将他依次合并 
	while(x1<=r1){
		b[t++]=a[x1++];
	}
	while(x2<=r2){
		b[t++]=a[x2++];
	}
	//将排好b[]数组给a[] i指针控制a[] j指针控制b[] 
	for(int i=l1,j=1;i<=r2;i++,j++){
		a[i]=b[j];
	}
}
void f(int l,int r){//并操作 
	int m;
	if(l==r)	return ;
	else{
		m=(l+r)/2; //取整个数组的中间位置 
		f(l,m); //进行递归分左部分 l为左指针 m为右指针 
		f(m+1,r); //进行递归分右部分 m+1为左指针 r为右指针
	}
	h(l,m,m+1,r); //进行调用归操作函数 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	f(1,n);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}