基本思想

归并排序：将两个或两个以上的有序子序列“归并”为一个有序序列。

在内部排序中，通常采用的是2-路归并排序。
即：将两个位置相邻的有序子序列R[/…m]和R[m+1…n]归并为一个有序序列R[/…n]。

2-路归并排序

2-路归并排序中的核心操作是，将待排序序列中前后相邻的两个有序序列归并为一个有序序列。

相邻两个有序子序列的归并

设两个有序表存放在同一数组中相邻的位置上： R[low … mid]和 R[mid + 1…high], 每次分别从两个表中取出一个记录进行关键字的比较，将较小者放入 T[low… high]中，重复此过程，直至其中一个表为空 ， 最后将另一非空表中余下的部分直接复制到T中。

void Merge{RedType R[],RedType &T[],int low,int mid,int high) 
{	// 将有序表 R[low.. mid]和R[mid+1..high]归并为有序表 T[low.. high]
	i=low;j=mid+1;k=low; 
	while(i<=mid&&j<=high) 					// 将R中记录由小到大地并入T中
	{
		if(R[i].key<=R[j].key) T[k]=R[i++]; 
		else T[k]=R[j++]; 
	}
	while(i<=mid) T[k++]=R[i++]; 			// 将剩余的 R[low.. mid]复制到 T中
	while (j<=high) T[k++]=R[j++]; 			// 将剩余的 R[j.high]复制到 T 中
1
2
3
4
5
6
7
8
9
10

归并排序

2-路归并排序将 R[low… high]中的记录归并排序后放入 T[low… high]中。 当序列长度等千 1 时，递归结束， 否则：
① 将当前序列一分为二， 求出分裂点 mid = (low+high)/2；
② 对子序列 R[low… mid]递归，进行归并排序，结果放入 S[low… mid]中；
③ 对子序列 R[mid + 1…high]递归，进行归并排序， 结果放入 S[mid + 1…high]中；
④ 调用算法 Merge, 将有序的两个子序列 S[low… mid]和 S[mid + 1… high]归并为一个有序的序列 T[low… high]。

void MSort(RedType R[],RedType &T[],int low,int high) 
{	//R [low .. high]归并排序后放人 T[low.. high]中
	if(low==high) T[low]=R[low]; 
	else 
	{
		mid=(low+high)/2; 			// 将当前序列一分为二， 求出分裂点 mid
		MSort(R,S,low,mid); 		// 对子序列 R[low.. mid]递归归并排序， 结果放入S[low .. mid]
		MSort(R,S,mid+1,high);		// 对子序列 R[mid+1.. high]递归归并排序， 结果放人 S[mid+ 1. . high]
		Merge(S,T,low,mid,high);	// 将S[low .. mid]和S[mid+1. .high]归并到 T[low .. high]
	}
}

void MergeSort(SqList &L) 
{	// 对顺序表 L 做归并排序
	MSort(L.r,L.r,1,L.length);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度：
当有n个记录时， 需进行log₂n趟归并排序， 每一趟归并， 其关键字比较次数不超过n , 元素移动次数都是n, 因此， 归并排序的时间复杂度为O(nlog₂n)。

空间复杂度：
用顺序表实现归并排序时， 需要和待排序记录个数相等的辅助存储空间， 所以空间复杂度为O(n)。

算法特点：
(1)是稳定排序。
(2)可用于链式结构， 且不需要附加存储空间，但递归实现时仍需要开辟相应的递归工作栈。