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

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

}