归并模板

归并大概思路：从中间分解直到只剩一个（分解不了），再排序合并（如图）

上代码

#include<bits/stdc++.h>
using namespace std;
int n;
//合并
void AndSort(vector<int>& vec,int l,int m,int r){
    int *tmp=new int[r-l+1];
    int i=l,j=m+1,ind=0;
    while(i<=m&&j<=r){
        if(vec[i]<=vec[j])tmp[ind++]=vec[i++];
        else tmp[ind++]=vec[j++];
    }
    //可能出现合并时其中一边大于两个（有剩余）
    while(i<=m)tmp[ind++]=vec[i++];
    while(j<=r)tmp[ind++]=vec[j++];
    for(int i=0;i<ind;i++){
        vec[l+i]=tmp[i];
    }
    //因为tmp是临时数组，所以要记得清空
    delete[] tmp;
}
//分解
void Up2down(vector<int>& vec,int l,int r){
    if(l>=r)return;
    int m=(l+r)/2;
    Up2down(vec,l,m);//左递归
    Up2down(vec,m+1,r);//右递归
    //分解后合并
    AndSort(vec,l,m,r);
    for(int i=0;i<n;i++){
        cout<<vec[i]<<" ";
    }
    cout<<endl;
    return;
}
int main(){
    cin>>n;
    vector<int> vec;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        vec.push_back(x);
    }
    Up2down(vec,0,vec.size()-1);
}