归并排序非递归算法最通俗易懂的解析
分析：
非递归，即迭代，与递归最大的区别在于实现的方向不同。递归拆开来是“递推”与“回归”，也就是先从顶层往下，逐层递推到底层，再从底层逐层回归到顶层，所以mergesort的递归版本是先从顶层开始往下不断对数组一分为二，到底层归并，回到上一层，再归并，重复直到顶层。非递归是从底层开始不断往上迭代，mergesort的迭代版本是从底层开始，对左边k个右边k个元素归并，换下一段，再对左右两边k个元素局部归并，直到数组末尾，如果有剩余，最后再归并左边k个和右边剩余的元素一次，k乘以2，这样算一次迭代，下一次遍历数组，对2k个元素局部归并，直到nk不小于数组长度，到达顶层，结束。
代码：
#include<iostream>
#include<cstdlib>
#define SIZE 30
#define RANDOM 100
using namespace std;
int *b=new int[SIZE];//开头先定义临时数组
void MergeNonRec(int *elem,int lo,int mi,int hi)
{//对elem数组的[lo,mi),[mi,hi)部分合并，注意右边是开区间
int lb=mi-lo;
int lc=hi-mi;
int *a=elem+lo;//a从elem的lo开始改变elem
int *c=elem+mi;//c从elem+mi开始到elem+hi的部分将与elem+lo到elem+mi作对比
for(int i=0;i<lb;b[i]=a[i++]);//b接收elem+lo到elem+mi的部分与c对比
for(int i=0,j=0,k=0;j<lb||k<lc;)//b与c对比完存入a
{
if(j<lb&&(lc<=k||b[j]<c[k]))a[i++]=b[j++];
if(k<lc&&(lb<=j||c[k]<=b[j]))a[i++]=c[k++];
}
}
void MergePass(int *elem,int k,int len)
{
int i=0;
while(i+2*k<=len)//遍历数组
{
MergeNonRec(elem,i,i+k,i+2*k);//每次对左边k个和右边k个元素归并
i+=2*k;//合并完两个k个元素的部分后，指针位移2k个单位
}
if(i+k<=len)//若有剩余数据则将剩余部分再归并一次，即左边k个右边len-i-k个
MergeNonRec(elem,i,i+k,len);
}
void MergeSortNonRec(int *elem,int len)
{
int k=1;//定义步长，即合并元素个数
while(k<len)
{
MergePass(elem,k,len);//遍历数组并局部归并k个元素，即左边k个右边k个
k*=2;//两端的k个元素归并完，再对两端2k个元素归并
}
}
int main()
{
srand(time(NULL));
int a[SIZE];
for(int i=0;i<SIZE;i++)
a[i]=rand()%RANDOM;
cout<<"Before:";
cout<<a[0];
for(int i=1;i<SIZE;i++)
cout<<' '<<a[i];
MergeSortNonRec(a,SIZE);
cout<<"After:";
cout<<a[0];
for(int i=1;i<SIZE;i++)
cout<<' '<<a[i];
cout<<endl;
return 0;
}
