11.5 非递归的归并排序

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n;

int help[1008611];
int arr[1008611];


void merge(int l,int m,int r){
    int i=l;
    int a=l;
    int b=m+1;
    while(a<=m&&b<=r){
        help[i++]=arr[a]<=arr[b]?arr[a++]:arr[b++];
    }

    while(a<=m){
        help[i++]=arr[a++];
    }
    while(b<=r){
        help[i++]=arr[b++];
    }
    for (int j = l; j <=r ; ++j) {
        arr[j]=help[j];
    }
}

void solve(){

    for(int l,m,r,step=1;step<n;step<<=1){

        l=0;
        while(l<n){
            m=l+step-1;
            if(m+1>=n){
                break;
            }
            r=min(l+(step<<1)-1,n-1);
            merge(l,m,r);
            l= r+1;
        }
    }
}



int32_t main() {
    cin>>n;
    for (int i = 0; i <n ; ++i) {
        cin>>arr[i];
    }
    solve();

    for (int i = 0; i < n; ++i) {
        cout<<arr[i];
    }
    return 0;
}