Iterative Implementation of Merge Sort (Reference)

This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

Recursive merge sort is very space and time consuming, whereas the non-recursive algorithm is different — its minimum additional space complexity is O(N). Professor Chen Yue’s MOOC explains it very clearly~ Click here Here I’ll just present the code with comments directly.

#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)
        //找每一对要归并的子序列 直到倒数第二对
        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;
}