C语言递归实现二路归并排序

二路归并意即需要将一个数组分成两个有序部分再归并，分成的两个部分再各自分成两个部分并有序化后再归并，如此往复直到最后每个部分只有1个元素，自然就有序了。这里，我们可以先将一个数组分为两个部分--左半部分，右半部分。两个部分都有序化后，用另一个函数连接这两个部分。这样，最终就实现了二路归并。

函数代码样例如下：其中，MergeSort是递归实现的，要调用子函数MergeArray，而MergeArray将两个有序数组按大小合并连接。注意标准库中有Merge函数，因此函数命名时不要命名为Merge。MergeSort中head tail顾名思义是数组的开始下标和结束下标，数组首元素从零开始。MergeArray中head1 tail1是左半部分待排序数组的头尾下标，head2 tail2是右半部分待排序数组头尾下标，实际上，head2=tail1+1但为了直观点还是将其写入了参数。由于排序时需要一个数组暂存，所以开辟一个数组空间，结束后销毁。这样比主函数定义一个辅助数组要干净利落一些。

int MergeSort(int a[],int head,int tail)
{
	int i=0,j=0;
	if(head<tail)
	{
		MergeSort(a,head,(head+tail)/2);
		MergeSort(a,(head+tail)/2+1,tail);
		MergeArray(a,head,(head+tail)/2,(head+tail)/2+1,tail);

	}
}

int MergeArray(int a[],int head1,int tail1,int head2,int tail2)
{
	int i=head1,j=head2,k=0;
	int *p=(int *)malloc(sizeof(int)*(tail2-head1+1));
	int *point=p;
	while(i<=tail1&&j<=tail2)
	{
		if(a[i]<=a[j])p[k++]=a[i++];
		else p[k++]=a[j++];
	}
	while(i<=tail1)p[k++]=a[i++];
	while(j<=tail2)p[k++]=a[j++];
	for(k=0;k<=tail2-head1;k++)a[head1+k]=p[k];
	free(point);

}