归并排序(Merge sort)

gaunthan Posted on Aug 7 2016

? Sorting ? ? Algorithm ?

## 思想
**归并排序**（Merge sort）是建立在归并操作上的一种有效的排序算法，它以 $O(nlogn)$ 最坏情形运行时间运行。它是采用**分治法**(divide-and-conquer)的一个非常典型的应用，通过将已有序的子序列合并，以得到完全有序的序列。排序过程的思路为：

1. 先使每个子序列有序；
2. 再使子序列段间有序。

对于一个需要排序的数组$A[0..n-1]$，归并排序将它一分为二：$A[0..\lfloor n/2 \rfloor -1]$和$A[\lfloor n/2 \rfloor..n-1]$，并对每个子数组递归排序，然后把这两个排好序的子数组合并为一个有序数组。

若将两个有序表合并成一个有序表，称为**二路归并**。归并排序可并行实现。

## 示例
归并排序示例图如下：

![](https://leanote.com/api/file/getImage?fileId=587cdc06ab644174c5000184)

首先是对序列进行分组，直到每个组只含有1个元素，这时候开始合并过程。每一次合并过程都会生成长度为两个分组长度之和的新分组，然后把生成的新分组作为合并的一个参数，继续合并过程，直到该分组的长度等于输入序列的长度。

你也可以通过查看下面的动态图来获得直观的感受：

![](https://leanote.com/api/file/getImage?fileId=587f4163ab644166160003b5)

图片来自[Merge sort - Wikipedia](https://en.wikipedia.org/wiki/Merge_sort)。

## 效率分析
归并排序的效率如何呢？为简单起见，假设输入规模$n$是2的乘方，那么键值比较次数$C(n)$的递推关系式为：

$$ 当 n > 1 时，C(n) = 2C(n/2) + C_{Merge}(n)，C(1) = 0$$

在合并阶段(Merge)，我们每做一步都要进行一次比较，比较之后，两个数组中尚需处理的元素总个数减1。在最坏情况下，无论哪个数组都不为空，除非另一个数组只剩下最后一个元素。因此，对于最坏情形来说，$C_{Merge}(n) = n-1$，因此有以下递推式：

$$ 当 n > 1 时，C_{worst}(n) = 2C_{worst}(n/2) + n-1，C(1) = 0$$

根据[分治算法主定理](http://leanote.com/blog/post/58a7b354ab6441489f003b6f)，$C_{worst}(n) \in \theta(nlogn)$。实际上，如果$n=2^k$，很容易求得该最差效率递推式的精确解为：
$$C_{worst}(n) = nlog_2n - n + 1$$

归并排序在最坏情况下的键值比较次数十分接近基于比较的排序算法在理论上能够达到的最少次数。当$n$很大时，归并排序算法比较的次数是要小于$0.25n$次的，因此效率也属于$\theta(nlogn)$。

相比于快速排序和堆排序，**归并算法的一个显著优点在于其稳定性**，主要缺点在于需要线性的额外空间。归并算法也可以做到原地排序，使空间复杂度降至 $O(1)$，但算法比较复杂，具体见后文。

归并排序有两类主要的变化形式：

- 算法自底向上合并数组的一个个元素对，然后再合并有些有序对，依次类推。这种方式是迭代式的，因此避免了使用堆栈处理递归调用时的空间和时间开销。
- 算法把数组划分为待排序的多个部分，再对它们递归排序，最后将其合并在一起。这个方案尤其适合对存放在二级存储空间（内存-外存）的文件进行排序，也被称为**多路归并排序**(multiway mergesort)。

## 实现
### 合并操作
基本的合并算法是取两个输入数组 A 和 B、一个输出数组 C，以及三个计数器 Aptr， Bptr， Cptr。它们初始置于对应数组的开始端。A[Aptr]和 B[Bptr]中的较小者被拷贝到 C 中的下一个位置，相关的计数器向前推进一步。当两个输入表有一个用完时，则将另一个表中剩余部分拷贝到 C 中。

如果对 Merge 的每个递归调用均局部声明一个临时数组，那么在任一时刻就可能有 log N 个临时数组处在活动期，这对于小内存机器是致命的。另一方面，如果 Merge 例程动态分配并释放最小量临时内存，那么由 malloc 占用的时间会很多。因此，可将输入数组分成两个输入数组，其中一个作为临时存储空间：
```cpp
// 对数组a的两个有序分组a[leftPos, rightPos - 1]和a[rightPos, rightEnd]进行合并操作。
//  结果首先暂存到tmpArray中，最后拷贝回数组a
void Merge(ElementType a[], ElementType tmpArray[], unsigned leftPos, 
            unsigned rightPos, unsigned rightEnd)
{
	int tmpPos = leftPos;
	const int leftEnd = rightPos - 1;
	const int leftPosBackup = leftPos;
	// main loop
	while (leftPos <= leftEnd && rightPos <= rightEnd)
		if (a[leftPos] < a[rightPos])
			tmpArray[tmpPos++] = a[leftPos++];
		else
			tmpArray[tmpPos++] = a[rightPos++];
	// get rest of first half
	while (leftPos <= leftEnd)
		tmpArray[tmpPos++] = a[leftPos++];
	// get rest of second half
	while (rightPos <= rightEnd)
		tmpArray[tmpPos++] = a[rightPos++];
	// copy elements to input array
	while (rightEnd >= leftPosBackup) {
		a[rightEnd] = tmpArray[rightEnd];
		--rightEnd;
	}
}
```

### 归并排序
#### 递归实现
```cpp
// 归并排序主算法，对数组a[left, right] 进行归并排序，使用了暂存数组tmpArray
void MSort(ElementType a[], ElementType tmpArray[], 
                const unsigned left, const unsigned right)
{
    int center;
    if(left >= right) return;
    
    center = left + (right - left) / 2;
    MSort(a, tmpArray, left, center);
    MSort(a, tmpArray, center + 1, right);
    Merge(a, tmpArray, left, center + 1, right);
}
```

#### 迭代实现
```cpp
void MSort(ElementType a[], ElementType tmpArray[], 
                const unsigned left, const unsigned right)
{
	const unsigned maxGroupLength = right - left + 1;
	unsigned groupLength = 1;
	unsigned leftBegin, rightBegin, rightEnd;
	
	for (; groupLength < maxGroupLength; groupLength *= 2) {
		leftBegin = left, rightBegin = left + groupLength;
		
		while (rightBegin <= right) {
			rightEnd = rightBegin + groupLength - 1;
			if(rightEnd > right)
			    rightEnd = right;
			Merge(a, tmpArray, leftBegin, rightBegin, rightEnd);
			leftBegin = rightEnd + 1;
			rightBegin = leftBegin + groupLength;
		}
	}
}
```

### 算法主体
```cpp
// 归并排序算法，封装了开辟临时存储空间的操作
void MergeSort(ElementType a[], unsigned n)
{
    ElementType *tmpArray;
    if(n <= 1) return;
    
    tmpArray = (ElementType *)malloc(sizeof(ElementType) * n);
    if (tmpArray == NULL) { // 无内存用于临时存储，出错返回
        errors("MergeSort: Memory overflow.");
        return;
    }
    MSort(a, tmpArray, 0, n - 1);
    free(tmpArray);
}
```

## 常数级空间复杂度
我们知道，按理来说归并排序的空间复杂度是$O(n)$，毕竟我们需要使用一个大小为 n 的临时数组。然而，实际上这个临时数组是可以避免的。

考虑序列 S: 1 2 3 5 3 4 5 6，我们将它看成两个长度皆为4的子序列。一开始我们让 begin = 0, mid = 4，然后执行以下步骤：

- 递增 begin 直到 begin == mid 或者 S[begin] > S[mid]。对于这个例子，begin 在执行完该操作后，值为3。
- 接着保存 mid 到 tmp，然后递增 mid，直到 mid 到达序列尾后或者满足 S[mid] >= S[begin]。对于这个例子，mid 为6。
- 在这两个步骤后，我们得到序列 S[begin..tmp-1] 和 S[tmp, mid - 1]，即 5 和 3 4，通过使用“翻手准则”，我们原地交换(exchange)这两个序列，得到 3 4 5，即原序列 S 将变为 1 2 3 3 4 5 5 6，我们继续前两步，直到 begin 等于 mid，这意味着 begin 所在的序列全部都小于或等于 mid 所在的序列，因此合并过程结束。

通过使用“翻手准则”，我们成功避免使用临时数组，使得归并排序的空间复杂度降低到$O(1)$。相关代码的实现，可以参考[《归并排序及其空间复杂度的思考》](http://blog.csdn.net/u013074465/article/details/42043967)一文，但我认为文章中的判断写的略有问题。下图是该文中对上述过程的实现：
![](https://leanote.com/api/file/getImage?fileId=58e1a841ab644137790074a1)

与我所描述的不同之处在于第二步：我的是直到满足 S[mid] >= S[begin]，即如果 S[mid] < S[begin] 则一直递增；而该文是 S[mid] <= S[begin] 则一直递增。考虑序列 1 3 5 2 3 6，如果按照我的做法， 两个3的相对位置不变，而如果按照该文章所描述的做法，则相对位置会改变，这直接导致归并排序成为不稳定排序，显然这是我们不愿看到的。在考虑比较操作时，需要细心思考比较操作中的等于号是否会影响算法的稳定性。

## References

- MarkAllenWeiss, 韦斯. 数据结构与算法分析:C语言描述[M]. 机械工业出版社, 2010.
- 莱维汀, A.). 算法设计与分析基础(第3版)[M]. 清华大学出版社, 2015.
- [归并排序及其空间复杂度的思考](http://blog.csdn.net/u013074465/article/details/42043967)