归并排序循环实现（存用）

递归的归并排序是很占空间和时间的，而非递归算法就不一样了，额外空间复杂度最少为 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;
}

在这里插入图片描述