查看“︁归并排序”︁的源代码

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

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

{| class="wikitable"
! 比较时的两个队首 !! 取出 !! 已合成的前缀
|-
| <math>3_L,2</math> || 2 || <math>(2)</math>
|-
| <math>3_L,3_R</math> || <math>3_L</math> || <math>(2,3_L)</math>
|-
| <math>5,3_R</math> || <math>3_R</math> || <math>(2,3_L,3_R)</math>
|-
| <math>5,7</math> || 5 || <math>(2,3_L,3_R,5)</math>
|-
| <math>8,7</math> || 7 || <math>(2,3_L,3_R,5,7)</math>
|}

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

[[File:Gezhi-merge-sort-stable.svg|frame|center|alt=六个数八、左三、五、右三、二、七分为两半，各自排成左三五八和二右三七，再归并为二左三右三五七八|相等关键字先取左半的元素，最终仍保持左 3 在右 3 之前。]]

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

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

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

<math-experiment type="algorithm" demo="merge-sort" />

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

<div class="math-code-example">
<div class="math-code-language">Python 3</div>
<pre class="math-code-source" data-language="python">
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([]) == []
</pre>
</div>

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

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

== 参考资料 ==
* [https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/sorts/merge_sort.py TheAlgorithms/Python：merge_sort.py]；[https://github.com/TheAlgorithms/Python/blob/c27e95123cb7e2fef5b15e64b5e800201cc7665c/sorts/iterative_merge_sort.py 同仓库的迭代变体]。本文采用独立编写的下标合并实现。
* [https://algs4.cs.princeton.edu/22mergesort/ Sedgewick、Wayne，Mergesort]：归并、稳定性与比较模型下的时间界。
* 先修：[[算法与复杂度]]；对照：[[二分查找]]、[[快速排序]]。
[[分类:算法]]