マージソートのループ実装（保存用）

再帰的なマージソートは、スペースと時間を多く占有しますが、非再帰アルゴリズムは異なり、追加のスペースの複雑さは最小で O (N) です。
陳越姥姥の MOOC では、非常に明確に説明されています〜ここをクリック
ここでは、コードとコメントを直接掲載します

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int inf  = 0x3f3f3f;
int N;
ll a[maxn];
void swap(ll &a, ll &b){//交換a,bの値
    int tmp = a;
    a = b;
    b = tmp;
}
void Merge(ll a[],ll tmp[], int s, int m, int e) {
    //配列aの部分配列a[s,m-1]とa[m,e]を配列tmpにマージし、tmpがソートされた状態になるようにする
    int pb = s;
    int p1 = s, p2 = m;//p1は前半部分、p2は後半部分を指す
    while (p1 <= m-1 && p2 <= e) {
        if (a[p1] <= a[p2])
            tmp[pb++] = a[p1++];
        else 
            tmp[pb++] = a[p2++];
    }
    while(p1 <= m-1) 
        tmp[pb++] = a[p1++];
    while(p2 <= e) 
        tmp[pb++] = a[p2++];
    for (int i = 0; i < e-s+1; ++i)
        a[s+i] = tmp[i];
}
void Merge_Pass(ll a[], ll b[], int N, int len) {
    //配列aを長さlenで分割し、bにマージする
    //lenは現在のソート済み部分列の長さ
    int i;
    for(i = 0; i <= N - 2*len; i += 2*len) 
        //マージする各ペアを見つける 最後から2番目のペアまで
        Merge(a, b, i, i+len, i+2*len-1); //aをマージする
    if(i+len < N) //最後に2つの部分列がある場合
        Merge(a, b, i, i+len, N-1);
    else  //最後に1つのソート済み部分列が残る場合
        for(int j = i; j < N; ++j) b[j] = a[j];
}
void Merge_Sort(ll a[], int N) {
    int len = 1;//ソート済み部分列の長さを初期化
    ll *tmp;
    tmp = new ll[N];
    if(tmp != NULL) {
        while(len < N) {
            Merge_Pass(a, tmp, N, len);
            len *= 2;
            Merge_Pass(tmp, a, N, len);
            len *= 2;
        }
        delete [] tmp;
    } else printf("スペースが不足しています");
}
int main(){
    scanf("%d", &N);
    for(int i = 0; i < N; ++i) 
        scanf("%lld", &a[i]);
    Merge_Sort(a, N);
    for(int i = 0; i < N; ++i) {
        printf(" %lld"+!i, a[i]);
    }
    return 0;
}

在这里插入图片描述