归并排序循環實現（存用）

遞歸的归并排序是很佔空間和時間的，而非遞歸算法就不一樣了，額外空間複雜度最少為 O (N)。
陳越姥姥的慕課裡就講得很清楚～戳這兒
這裡就直接上代碼 + 註釋了

#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;
}

在這裡插入圖片描述