8645 归并排序（非递归算法）
如果你看到和我的贼相似的，那我就是抄的，别骂了
代码实现
#include <iostream>
using namespace std;
void merge(int *a,int start,int mid,int last)
{
int l=start;//两个小的数组，左边那个数组的第一个
int r=mid+1;//右边那个数组的第一个
int b[last-start+1],j=0;
//算法上有点像顺序表！！
while(l<=mid&&r<=last)
{
if(a[l]<=a[r]) b[j++]=a[l++];
else b[j++]=a[r++];
}
while(l<=mid) b[j++]=a[l++];
while(r<=last) b[j++]=a[r++];
//重新整理回a数组中
for(int i=0;i<j;i++) a[start++]=b[i];
}
void split(int *a,int span,int length)//按照span对整个数组逐步进行自下而上的合并
{
int cl=0;
while(cl+span*2-1<length)//右数组
{
merge(a,cl,cl+span-1,cl+span*2-1);
//两个两个一组合并，进入到下一组
cl+=2*span;
}
//到末尾时，剩余长度只够一个左表
if(cl+span-1<length-1) merge(a,cl,cl+span-1,length-1);
}
void mergesort(int *a,int length)//确定每一次合并的跨度span
{
int span=1;
while(span<length)//大于length的合并无意义
{
split(a,span,length);//按照这个跨度对整个数组逐步进行合并
for(int i=0;i<length;i++) printf("%d ",a[i]);//每完成一次合并打印一次
printf("\n");
span*=2;
}
}
int main()
{
int n,a[100];
scanf("%d",&n);
for(int i=0;i<=n-1;i++) scanf("%d",&a[i]);
mergesort(a,n);
}
思路
归并排序的思路实际是将大的数组（等元素结构…）分成若干小的数组结构，然后两两合并
合并的这个过程：比较大小->重新排列由两个数组组成的大数组（来自课本）
