图文详解：归并排序之c语言实现

归并排序采用“分”、“治”思想，将一数组按一定的方式拆分成若干个单元素，再将这些单个元素按一定的方式排序组合起来

那怎么“分”，怎么“治”呢？

如何“分”：通过上图可以看出，数组每次都是拆分成两个小数组，假设数组的第一个元素的下标设为low,最后一个元素的下标为high,则以mid（mid=((low+high)/2)）为界分开。

如何“治”：通过上图可以看出，“治”的方式为“合二为一”，但是如何让两个小数组里面较小的排前面呢？其实不难，通过遍历比较就可以了，例如上图的小数组{1，4}、{2，3，5}，
先让1依次和2、3、5比较，发现1最小，然后放到新数组的第一位，然后让4依次和2、3、5比，2、3比4小，所以依次放在新数组的第二、三位，5比4大，则先把4放到新数组的第四位，最后把5放到最后一位。

c代码实现

#include<stdio.h>
#include<stdlib.h>

void merge(int *a,int low,int mid,int high,int *b)
{
	int i,j;
	for(int k=low;k<=high;k++)
  	b[k]=a[k];
 	for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)//实现比较遍历
 	{
	 	 if(b[i]<=b[j])
	  	 a[k]=b[i++];
	 	 else
	  	 a[k]=b[j++];
	}
	 while(j<=high) a[k++]=b[j++];//把左子数组剩余的复制到数组里面
	 while(i<=mid)  a[k++]=b[i++];//把右子数组剩余的复制到数组里面
}
void mergesort(int *a,int low,int high,int *b)
{
	if(low<high)
 	{
	  int mid=(low+high)/2;
	  mergesort(a,low,mid,b);//右子数组
	  mergesort(a,mid+1,high,b);//左子数组
	  merge(a,low,mid,high,b);//开始“治”
	}
}




int main()
{
	int a[]={4,1,3,2,5};
 	int length=sizeof(a)/sizeof(int);
 	int *b=(int *)malloc(sizeof(int)*length);//辅助数组
 	mergesort(a,0,length-1,b);
 	for(int i=0;i<length;i++)
  		printf("%d ",a[i]);
 	printf("\n");
	 return 0;
}