分治思想

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+1;  //常量
int a[N],temp[N];//t:临时数组
void hb(int l,int r){
	int mid = (l+r)/2;
	int i=l,j=mid+1,k=l;
	while(i<=mid && j<=r){
		if(a[i]<a[j]){
			temp[k++]=a[i++];
		}else{
			temp[k++]=a[j++];
		}
	}
	while(i<=mid){	//当左边还有剩余的时候
		temp[k++] = a[i++];
	}
	while(j<=r){//当右边还有剩余的时候
		temp[k++] = a[j++];
	}
	//把临时数组复制到原数组
	for(int i=l;i<=r;i++){
		a[i] = temp[i];
	}
}
void gb(int left,int right){
	if(left>=right) return;
	int mid = (left+right)/2;	//中间值
	gb(left,mid);//左边
	gb(mid+1,right);//右边
	hb(left,right);//合并
}
int main(){
	//1.输入n和n个数
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	//归并排序
	gb(1,n);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	
	
	return 0;
}