归并排序

有三种排序算法：

• 归并排序（Merge-sort）
• 快速排序（Quicksort）
• 堆排序（Heap-sort）

这三种算法均接收一个输入数组 a，并将数组中的元素按非递减顺序排序，时间复杂度为 $O(n \log n)$（期望）。这些算法都是基于比较的。它们不关心所排序数据的具体类型；对数据唯一的操作是使用 compare(a, b) 方法进行比较。回顾一下，compare(a, b) 在 $a < b$ 时返回负值，在 $a > b$ 时返回正值，在 $a = b$ 时返回零。

本模块讨论对 $n$ 个元素进行排序的算法。这看似与数据结构课程无关，但其实有多个重要原因。最明显的原因是：其中两种排序算法（快速排序和堆排序）分别与我们已经学习过的两种数据结构（随机二叉搜索树和堆）密切相关。

排序基础

存在多种仅通过比较来实现排序的算法，且它们的时间复杂度均为 $O(n \log n)$。事实上，这三种算法在渐近意义上都是最优的；任何仅依赖比较的算法都无法避免在最坏情况下进行大约 $n \log n$ 次比较，平均情况也是如此。

在继续之前需要指出的是，任何集合（Set）或优先队列（Priority Queue）的实现也可以用来获得 $O(n \log n)$ 时间复杂度的排序算法。例如，我们可以对 $n$ 个元素执行 $n$ 次 add(x) 操作，然后在 BinaryHeap 或 MeldableHeap 上执行 $n$ 次 remove() 操作完成排序。或者，我们可以将 $n$ 个元素依次添加到任意一种二叉搜索树数据结构中，再通过中序遍历提取出有序的元素。然而，在这两种方法中，我们都经历了大量开销来构建一个从未被完全利用的数据结构。由于排序是一个极其重要的问题，因此值得开发直接、高效、简洁且空间利用率高的专门方法。

如果允许除比较之外的其他操作，则结果将完全不同。实际上，通过使用数组索引，可以在 $O(cn)$ 时间内对范围在 $\{0, ..., n^c - 1\}$ 内的 $n$ 个整数进行排序。

归并排序 是递归分治策略的经典范例：如果数组 a 的长度不超过 1，则它已有序，无需处理。否则，我们将 a 分成两个部分：a0 = a[0], ..., a[n/2 - 1] 与 a1 = a[n/2], ..., a[n - 1]。我们递归地对 a0 和 a1 进行排序，然后将这两个已排序的子数组合并，得到最终的完整有序数组 a：

1def merge_sort(a):
2    if len(a) <= 1:
3        return a
4    m = len(a) // 2
5    a0 = merge_sort(a[:m])
6    a1 = merge_sort(a[m:])
7    merge(a0, a1, a)
8    return a

可视化演示

下图展示了一个示例：

相比排序，合并两个已排序的数组 a0 与 a1 相对简单。我们逐个将元素加入 a。如果 a0 或 a1 为空，则从另一个非空数组中取出下一个元素。否则，取 a0 和 a1 中下一个元素的较小者，并将其加入 a：

1def merge(a0, a1, a):
2    i0 = i1 = 0
3    for i in range(len(a)):
4        if i0 == len(a0):
5            a[i] = a1[i1]
6            i1 += 1
7        elif i1 == len(a1):
8            a[i] = a0[i0]
9            i0 += 1
10        elif a0[i0] <= a1[i1]:
11            a[i] = a0[i0]
12            i0 += 1
13        else:
14            a[i] = a1[i1]
15            i1 += 1

注意，merge(a0, a1, a) 算法在其中一个数组耗尽元素前最多进行 $n - 1$ 次比较。

归并排序的时间复杂度

为了理解归并排序的时间复杂度，最直观的方式是借助其递归树模型。假设目前 $n$ 是 2 的幂，即 $n = 2^{\log n}$，且 $\log n$ 为整数。如下图所示：

归并排序将排序 $n$ 个元素的问题分解为两个子问题，每个子问题规模为 $n/2$。这两个子问题又各自进一步分解为两个更小的问题，共四个规模为 $n/4$ 的子问题。这四个子问题再分解为八个规模为 $n/8$ 的子问题，依此类推。当到达最底层时，$n/2$ 个规模为 2 的子问题被转化为 $n$ 个规模为 1 的问题。对于每个规模为 $n/2^i$ 的子问题，合并与复制数据所需时间为 $O(n/2^i)$。由于共有 $2^i$ 个这样的子问题，因此在不计递归调用的情况下，所有规模为 $n/2^i$ 的子问题的总工作量为：

$$2^i \times O(n/2^i) = O(n)$$

因此，归并排序的总时间复杂度为：

$$\sum_{i=0}^{\log n} O(n) = O(n \log n)$$

以下定理的证明基于上述分析，但需稍作严谨处理以应对 $n$ 不是 2 的幂的情况。

定理：merge_sort(a) 算法运行时间复杂度为 $O(n \log n)$，且比较次数不超过 $n \log n$。

证明：采用数学归纳法。基本情况 $n = 1$ 显然成立——当输入数组长度为 0 或 1 时，算法直接返回，不进行任何比较。

合并两个总长度为 $n$ 的已排序列表最多需要 $n - 1$ 次比较。设 $C(n)$ 表示 merge_sort(a) 在长度为 $n$ 的数组上执行的最大比较次数。若 $n$ 为偶数，则根据归纳假设可得：

$$\begin{split} C(n) & \leq n - 1 + 2C(n/2) \\ & \leq n - 1 + 2((n/2) \log(n/2)) \\ & = n - 1 + n \log(n/2) \\ & = n - 1 + n \log n - n \\ & < n \log n \end{split}$$

当 $n$ 为奇数时，情况稍复杂。我们使用两个容易验证的不等式：

$$\tag{1} \log(x + 1) \leq \log x + 1$$

对所有 $x \geq 1$ 成立，以及

$$\tag{2} \log(x + 1/2) + \log(x - 1/2) \leq 2 \log x$$

对所有 $x \geq 1/2$ 成立。不等式 (1) 来源于 $\log x + 1 = \log(2x)$，而 (2) 则源于 $\log$ 函数的凹性。利用这些工具，对于奇数 $n$，有：

$$\begin{split} C(n) & \leq n - 1 + C(\lceil n/2 \rceil) + C(\lfloor n/2 \rfloor) \\ & \leq n - 1 + \lceil n/2 \rceil \log \lceil n/2 \rceil + \lfloor n/2 \rfloor \log \lfloor n/2 \rfloor \\ & = n - 1 + (n/2 + 1/2) \log(n/2 + 1/2) + (n/2 - 1/2) \log(n/2 - 1/2) \\ & \leq n - 1 + n \log(n/2) + (1/2)(\log(n/2 + 1/2) - \log(n/2 - 1/2)) \\ & \leq n - 1 + n \log(n/2) + 1/2 \\ & < n + n \log(n/2) \\ & = n + n(\log n - 1) \\ & = n \log n \end{split}$$

现在我们尝试对数组元素进行归并排序。

1# 归并排序函数
2def merge_sort(a):
3    if len(a) <= 1:
4        return a
5    m = len(a) // 2
6    a0 = merge_sort(a[:m])
7    a1 = merge_sort(a[m:])
8    merge(a0, a1, a)
9    return a
10
11# 归并排序辅助函数
12def merge(a0, a1, a):
13    i0 = i1 = 0
14    for i in range(len(a)):
15        if i0 == len(a0):
16            a[i] = a1[i1]
17            i1 += 1
18        elif i1 == len(a1):
19            a[i] = a0[i0]
20            i0 += 1
21        elif a0[i0] <= a1[i1]:
22            a[i] = a0[i0]
23            i0 += 1
24        else:
25            a[i] = a1[i1]
26            i1 += 1
27
28if __name__ == "__main__":
29    numbers = [5, 2, 9, 1, 3, 6]
30    print("原始数组:", numbers)
31    merge_sort(numbers)
32    print("排序后数组:", numbers)

说明

让我们从 main() 函数开始解释：

• 第 29 行：声明一个整型数组。
• 第 31 行：调用 merge_sort() 对数组进行排序，该函数返回排序后的数组。