归并排序

归并排序（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$ ，最多有 $⌈ \log_{2} n ⌉$ 层，所以按常数时间关键字比较计，时间为 $Θ (n \log n)$ ，不依赖初始排列；额外数组用 $O (n)$ 空间，递归栈另用 $O (\log n)$ 。若 key 自身计算很昂贵，上述分析应把关键字计算的成本也算进去，或预先计算关键字。

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

参考资料

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