归并排序

归并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

可以看到这种结构很像一棵完全二叉树，分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

合并相邻有序子序列

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。

实现

void merge(int array[],int start,int range,int mid)
{
  int aux[range-start+1],i,j,k;
  
  for(k=start;k<=range;k++)
    aux[k-start]=a[k];
  
  i=start;
  j=mid+1;
  for(k=start;k<=range;k++)
  {
  	if(i>mid)
  	{
  		a[k]=aux[j-start];
  		j++;
	}
	else if(j>range)
	{
		a[k]=aux[i-start];
		i++;
	}
	else if(aux[i-start]>aux[j-start])
	{
		a[k]=aux[j-start];
		j++;
	}
	else
	{
		a[k]=aux[i-start];
		i++;
	}
  }	
}
 
void merge_sort(int array[],int start,int range)
{
    range = range - 1
    if(start>=range)
	    return ;
	
	int mid=(start+range)/2;
	
	merge_sort(array,start,mid);
	merge_sort(array,mid+1,range);
	merge(array,start,range,mid);	
}