归并排序

归并排序（merge sort）把一列对象分成两半，各自排好序，再把两条有序列合成一条。真正需要说明的是“归并”：每次只比较两条序列尚未取出的第一个元素，就能确定下一位。本文按关键字从小到大排序，并在相等时保留原来的先后次序。

从两条有序列合成一条

取六张带编号的卡片 $(8,3_L,5,3_R,2,7)$，下标 L、R 只用于辨认两张数值相同的 3。先分成左半 $(8,3_L,5)$ 和右半 $(3_R,2,7)$；递归排好后分别为 $(3_L,5,8)$ 与 $(2,3_R,7)$。随后只看两个队首：

比较时的两个队首	取出	已合成的前缀
$3_L,2$	2	$(2)$
$3_L,3_R$	$3_L$	$(2,3_L)$
$5,3_R$	$3_R$	$(2,3_L,3_R)$
$5,7$	5	$(2,3_L,3_R,5)$
$8,7$	7	$(2,3_L,3_R,5,7)$

右半已经用尽后，接上左半的 8，得到 $(2,3_L,3_R,5,7,8)$。图把“分开排序”与“最后一次归并”放在同一处；相等的两张 3 中，来自左半的卡片先出。

相等关键字先取左半的元素，最终仍保持左 3 在右 3 之前。

有序前缀与稳定性

设两条待归并序列已经有序。归并过程中，输出前缀始终有序，并且恰由已取出的最小那些元素组成。开始时前缀为空。下一位必在两条序列的队首中：同一条序列中更靠后的元素不可能比队首更小。取较小队首便保持这个性质；一条序列用尽后，另一条余项本来有序，直接接上即可。

当两个队首关键字相同，选择左半的元素。每一半内部的相对顺序已经由递归保持；两张原本跨半区的相等卡片，左边那张在原输入中也更早。因此排序是稳定的：关键字相等的元素保持输入次序。若在相等时先取右边，示例中的 $3_R$ 就会跑到 $3_L$ 前面，排序数值仍正确，但稳定性消失。

长度为 0 或 1 的序列已排序。假设两半经递归得到有序且稳定的结果，上面的归并性质使整段有序且稳定；逐层回到原序列，便得到正确结果。这是按序列长度进行的归纳，而不是仅凭图像观察。

归并排序的最后一次合并

比较两条有序序列的队首，观察相等关键字的先后次序。

打开交互演示

静态配图与完整推导见本节正文；交互演示需浏览器启用 JavaScript。

Python 实现

函数返回新列表，不改动输入。key 指定比较用的关键字；合并时只移动下标，不从 Python 列表头部反复删除元素，因此归并一段长度为 $m$ 的数据只做 $O(m)$ 次读取、比较和写入。

Python 3

def merge_sort(items, key=lambda item: item):
    data = list(items)
    buffer = data.copy()

    def sort(lo, hi):
        if hi - lo <= 1:
            return
        mid = (lo + hi) // 2
        sort(lo, mid)
        sort(mid, hi)
        i, j = lo, mid
        for k in range(lo, hi):
            if i == mid:
                buffer[k] = data[j]
                j += 1
            elif j == hi:
                buffer[k] = data[i]
                i += 1
            elif key(data[j]) < key(data[i]):
                buffer[k] = data[j]
                j += 1
            else:
                buffer[k] = data[i]
                i += 1
        data[lo:hi] = buffer[lo:hi]

    sort(0, len(data))
    return data


if __name__ == "__main__":
    cards = [(8, "a"), (3, "L"), (5, "a"),
             (3, "R"), (2, "a"), (7, "a")]
    answer = merge_sort(cards, key=lambda card: card[0])
    assert answer == [(2, "a"), (3, "L"), (3, "R"),
                      (5, "a"), (7, "a"), (8, "a")]
    assert cards[0] == (8, "a")
    assert merge_sort([]) == []

比较次数、空间和适用范围

每一层的所有归并段总长是 $n$，最多有 $\lceil {\log }_{2}n\rceil$ 层，所以按常数时间关键字比较计，时间为 $\Theta (n\log n)$，不依赖初始排列；额外数组用 $O(n)$ 空间，递归栈另用 $O(\log n)$。若 key 自身计算很昂贵，上述分析应把关键字计算的成本也算进去，或预先计算关键字。

稳定排序适合先按次要字段排，再按主要字段排的资料整理，因为后一步不会打乱主要字段相同时的原有次序。归并排序需要保存辅助数据；只要求原地改写且空间极紧时，还应比较其他排序方法的条件与代价。

参考资料

• TheAlgorithms/Python：merge_sort.py；同仓库的迭代变体。本文采用独立编写的下标合并实现。
• Sedgewick、Wayne，Mergesort：归并、稳定性与比较模型下的时间界。
• 先修：算法与复杂度；对照：二分查找、快速排序。