1.算法简述

归并排序是分治法的一种典型算法。一开始将有n个元素的待排序表看作n个子表，子表的表长为1。接下来，将n个子表依次两两归并为n/2个子表，此时这n/2个子表的表长变为2。再将n/2个子表归并为n/4个……如此归并，直至只有一个表。

对待排序表(26,5,77,1,61,11,59,15,48,19)，归并排序过程如下：

/*the two sorted initList[i:m] and initList[m+1:n] are merged 
into the sorted mergeList[i:n]*/
void merge(int initList[],int mergeList[],int i,int m,int n)
{
	int j,k,t;
	j=m+1;
	k=i;
	while(i<=m&&j<=n)
	{
		if(initList[i]<initList[j])
			mergeList[k++]=initList[i++];
		else mergeList[k++]=initList[j++];
	}
	if(i>m)
		for(t=j;t<=n;t++)
			mergeList[t]=initList[t];
	else
		for(t=i;t<=m;t++)
			mergeList[k+t-i]=initList[t];
}

/*perform one pass of the merge sort, n is the number of elements 
in the list, s is the size of each segment*/
void merge_pass(int initList[],int mergeList[],int n,int s)
{
	int i;
	for(i=1;i<=n-2*s+1;i+=2*s)
		merge(initList,mergeList,i,i+s-1,i+2*s-1);
	if(i+s-1<n) merge(initList,mergeList,i,i+s-1,n);
	else 
		for(;i<=n;i++)
			mergeList[i]=initList[i];
}

void merge_sort(int a[],int n)
{
	int extra[MAX];
	int s=1;           //initial segment size
	while(s<n)
	{
		merge_pass(a,extra,n,s);
		s*=2;
		merge_pass(extra,a,n,s);
		s*=2;
	}
}

2.Referrence

[1] Horowitz, et al., 《数据结构基础》, 清华出版社.

【算法】归并排序,布布扣,bubuko.com

【算法】归并排序

原文：http://blog.csdn.net/keyboardlabourer/article/details/22648617