归并排序的非递归写法

#include<iostream>
using namespace std;
const int N = 1e5 + 11;
int b[N], tmp[N];
int n;
/*归并排序的非递归写法*/

void ms(){
    int step = 1;//step表示每个序列的长度
    bool got = false;
    while(n / step){// n / step 表示目前有多少个序列
        for(int l = 0; l < n; l += 2*step){//for循环每一组，每一组有两个序列
         //l表示这两个子序列中第一个序列
        //的开头位置，用p1指向，l + step表示第二个
        //子序列的开头位置，用p2指向
            int p1 = l, p2 = l + step, k = 0; 
            while(p1 < l + step && p2 < l + 2*step && p1 < n && p2 < n){
                if(b[p1] < b[p2]) tmp[k ++] = b[p1 ++];
                else tmp[k ++] = b[p2 ++];
            }
            while(p1 < n && p1 < l + step) tmp[k ++] = b[p1 ++];
            while(p2 < n && p2 < l + 2*step) tmp[k ++] = b[p2 ++];
            for(int i = l, k = 0; i < n && i < l + 2*step; i ++, k++) b[i] = tmp[k];
        }
        step *= 2;
    }
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &b[i]);
    ms();
    for(int i = 0;i < n; i++) cout << b[i] << " ";
    return 0;
}