归并排序的迭代及递归实现

        归并排序迭代实现：归并排序，将输入表看做n个有序长度为1的子表，第一趟子表两两归并，生成n/2个长度为2的子表，依次归并子表，子表数目依次减半，直至仅有一个子表，结束；

//归并 inilist表的有序的两段  [start,mid] ,(mid,end] 到Mergelist中
void Merge(int *inilist,int*Mergelist,int start,int mid,int end)
{
	if (!inilist&&!Mergelist)
		return;
	int i=start,j=mid+1,index=start;
	while(i<=mid&&j<=end)
	{
		if(inilist[i]<=inilist[j])
		{
			Mergelist[index]=inilist[i];
			i++;
		}
		else
		{
			Mergelist[index]=inilist[j];
			j++;
		}
		index++;
	}
	while(i<=mid){Mergelist[index++]=inilist[i++];}
	while(j<=end){Mergelist[index++]=inilist[j++];}
}
//对inilist表按子表步长为step  [0,step-1] ,[step,2*step-1] , 归并到Mergelist中
void Mergepass(int *inilist,int *Mergelist,int len,int step)
{
	if(!inilist&&!Mergelist) return;
	int index=0;//下一个待归并段开始指针
	while(index<len)//还有分段要归并
	{
		if(index+2*step<=len)//还有两个 step（段） 以上
		{
			Merge(inilist,Mergelist,index,index+step-1,index+2*step-1);
			index+=2*step;
		}
		else if (index+step<=len)// 还有多于一个step（段）
		{
			Merge(inilist,Mergelist,index,index+step-1,len-1);
			index=len;
		}
		else//不到一段，无需归并，直接拷贝
		{
			while(index<len){Mergelist[index]=inilist[index];index++;}
		}
	}
}


void MergeSort(int *inilist,int len)
{
	int *Mergelist=new int[len];
	int step=1;//步长
	while (step<len)//不止一段
	{
		Mergepass(inilist,Mergelist,len,step);
		step*=2;
		Mergepass(Mergelist,inilist,len,step);//保证最后的结果肯定还会存放到 inilist中
		step*=2;
	}
	delete[] Mergelist;
}

归并排序递归实现：首先把表分为大小相等的两部分，成为左子表和右子表，然后递归第对子表进行排序，最后对完成排序的子表归并；

void RecursionSort(int *data,int start ,int end)
{
	if (!data||(start>=end))//递归终止条件
		return ;

	int mid=(start+end)/2;//分段中间点 [start,mid] , (mid,end] 两段; 
	//对子段递归
	RecursionSort(data,start,mid);
	RecursionSort(data,mid+1,end);
	
	//归并已经有序的子段
	int *Mergelist=new int[end-start+1];
	int i=start,j=mid+1,index=0;
	while (i<=mid&&j<=end)//归并
	{
		if (data[i]<=data[j])
		{
			Mergelist[index]=data[i];
			i++;
		} 
		else
		{
			Mergelist[index]=data[j];
			j++;
		}
		index++;
	}
	while(i<=mid){Mergelist[index++]=data[i++];}
	while(j<=end){Mergelist[index++]=data[j++];}

	for (int k=start,l=0;k<=end;k++,l++)
	{
		data[k]=Mergelist[l];
	}
	delete[] Mergelist;
}

测试：

#include <iostream>
using namespace std;
int main(int argc,char **argv)
{
	int data[5]={4,24,17,1,6};
	//MergeSort(data,5);
	
	RecursionSort(data,0,4);
	for(int i=0;i<5;i++)
		cout<<data[i]<<' ';
	cout<<endl;

	return 0;
}

如上，归并排序的原理值得深入理解；