归并排序 · aiwiki.page

归并排序是一种排序算法，通过先对序列中的较小部分排序，再将这些部分合并，使整个序列有序。它是分治法的经典例子：将输入分为两部分，分别排序，然后合并结果。在比较和元素移动均耗时常数的假设下，标准的数组实现需要 $\Theta(n\log n)$ 时间和 $\Theta(n)$ 辅助空间。归并排序可以保持关键字相同的元素在原序列中的相对顺序，因此可以实现稳定排序。(algs4.cs.princeton.edu)

基本原理与归并操作

核心操作是归并：将两个已经有序的序列合并为一个包含二者全部元素的有序序列。分别在两个序列的开头设置一个当前位置，比较这两个位置上的元素，并输出其中较小的一个。随后，将取出该元素的序列的当前位置向后移动。当其中一个序列的元素全部处理完毕后，将另一个序列剩余的元素追加到结果中。(xlinux.nist.gov)

例如：

左侧：  [2, 5, 8]
右侧：  [1, 5, 9]
归并后：[1, 2, 5, 5, 8, 9]

在每一步中，尚未处理的最小元素必然位于两个有序输入序列中某一个的当前位置。因此，选取两个当前元素中较小的一个，就能保持输出的有序性。这是归并过程所依据的核心循环不变量。对于长度分别为 $p$ 和 $q$ 的输入序列，如果需要将每个元素写入结果，归并耗时为 $\Theta(p+q)$ ；若两个输入序列都非空，则关键字比较次数最多为 $p+q-1$ 。(algs4.cs.princeton.edu)

自顶向下算法

自顶向下的版本使用递归。空序列或仅含一个元素的序列本身就是有序的。较长的序列则被分成两个大小近似相等的部分，分别递归排序，再将结果归并。这两部分的长度不必完全相同，因此算法不要求输入规模是二的幂。(algs4.cs.princeton.edu)

以下伪代码使用左闭右开区间：A[lo:hi] 包含下标 lo 对应的元素，但不包含下标 hi 对应的元素。它只分配一个辅助数组，并在整个递归过程中重复使用。

MERGE_SORT(A):
    B = 新建长度为 length(A) 的数组
    SORT_RANGE(A, B, 0, length(A))

SORT_RANGE(A, B, lo, hi):
    if hi - lo <= 1:
        return

    mid = lo + floor((hi - lo) / 2)
    SORT_RANGE(A, B, lo, mid)
    SORT_RANGE(A, B, mid, hi)
    MERGE(A, B, lo, mid, hi)

MERGE(A, B, lo, mid, hi):
    将 A[lo:hi] 复制到 B[lo:hi]
    i = lo
    j = mid

    for k = lo to hi - 1:
        if i == mid:
            A[k] = B[j]
            j = j + 1
        else if j == hi:
            A[k] = B[i]
            i = i + 1
        else if B[j] < B[i]:
            A[k] = B[j]
            j = j + 1
        else:
            A[k] = B[i]
            i = i + 1

这一实现采用标准的辅助数组方法。在归并之前复制输入区间，可以避免新写入的输出覆盖尚未处理的元素。关键字相等时选择左侧元素，则可保持稳定性。(algs4.cs.princeton.edu)

正确性与稳定性

算法的正确性可以对序列长度使用数学归纳法来证明。长度为零或一的序列满足排序要求。对于较长的序列，假设递归调用能够正确地对两个较小部分排序。归并随后生成一个有序序列，且其中恰好包含这两个部分的全部元素，由此证明原序列也得到了正确排序。(arxiv.org)

稳定排序会保持关键字相同的记录之间的相对顺序。考虑仅按数值字段排序的记录：

输入：[(3, a), (1, b), (3, c), (2, d)]
输出：[(1, b), (2, d), (3, a), (3, c)]

关键字为 3 的两条记录保持了原来的顺序。在归并排序中，要实现这一性质，既需要各部分内部的排序保持稳定，也需要在归并时采用适当的相等关键字处理规则。如果输入的两个部分在原序列中是连续的，那么在关键字相等时先取左侧元素，就能保持跨越两部分边界的原有顺序。因此，稳定性是具体实现的性质，并不是使用任意归并操作就会自动获得的性质。(algs4.cs.princeton.edu)

时间与空间复杂度

在均衡划分和线性时间归并的条件下，运行时间的递推关系为

T(n)=T(\lfloor n/2\rfloor)+T(\lceil n/2\rceil)+\Theta(n),

其中基本情形的耗时为常数。归并共有 $\Theta(\log n)$ 层，每个完整的归并层处理 $\Theta(n)$ 个元素。因此，普通实现的最佳、平均和最坏情况时间复杂度均为 $\Theta(n\log n)$ 。这些界限假设比较和元素复制的耗时均为常数。(cs.umd.edu)

对于包含 $n=2^k$ 个元素的标准自顶向下归并排序，最坏情况下的比较次数为

n\log_2 n-n+1.

将所有层中每次归并 $m$ 个元素所需的最多 $m-1$ 次比较相加，即可得到这一结果。(cs.umd.edu)

常见数组实现的空间复杂度如下：

资源	界限
归并辅助缓冲区	$\Theta(n)$
递归调用栈	$O(\log n)$
辅助空间总量	$\Theta(n)$

这些数值描述的是同一时刻占用内存的峰值，而不是整个执行过程中分配内存或移动元素的累计总量。重复使用同一个缓冲区，可以避免在每次递归调用时都单独分配一个与输入等大的缓冲区。(algs4.cs.princeton.edu)

在比较模型下，归并排序在渐近意义上是最优的。要区分 $n$ 个互不相同元素的所有可能排列，最坏情况下至少需要 $\lceil\log_2(n!)\rceil=\Omega(n\log n)$ 次比较。这一下界针对基于比较的排序；对于利用受限关键字表示方式的算法，不能原样套用。符号 $O$ 、 $\Omega$ 和 $\Theta$ 用于描述渐近增长，是大O记号及相关渐近记号的一部分。(algs4.cs.princeton.edu)

主要变体

自底向上归并排序

自底向上归并排序用逐轮处理代替递归划分。它先归并相邻的单元素有序段，再归并长度为二的有序段，接着归并长度为四的有序段，如此继续，直到整个输入形成一个有序段。最后一个有序段可能短于该轮规定的有序段长度。这一版本保留了标准的 $\Theta(n\log n)$ 时间界限和线性大小的数组缓冲区，同时不需要递归调用栈。(algs4.cs.princeton.edu)

自然归并排序

自然归并排序从输入中已有的有序子序列开始，而不是将每个元素视为一个独立的有序段。其性能取决于有序段的数量，以及算法如何安排这些有序段的归并顺序。包括 Timsort 在内的基于归并的自适应算法，会结合有序段检测与选择归并对象的规则。不同的归并策略可能具有不同的性能保证。(arxiv.org)

链表归并排序

对于链表，归并可以通过重新连接已有节点来完成，而不必将元素复制到辅助数组中。这就不再需要线性大小的数组缓冲区。其余控制空间的需求取决于具体实现：自顶向下版本可以使用对数深度的调用栈，而迭代实现则可以避免递归。Linux 内核提供了一种实用的稳定链表排序实现，其组织方式是依次进行归并。(kernel.googlesource.com)

原地数组变体

原地算法在输入所占空间之外只使用少量额外存储。数组归并可以使用远少于标准实现的辅助空间，但若要同时保持稳定性和高效的运行时间，实现就会更加复杂。因此，线性缓冲区是普通归并排序标准实现的特征，并不意味着所有基于归并的排序方法都不可能使用更少的空间。(algs4.cs.princeton.edu)

应用

外部排序

在数据量超过可用主存容量的外部排序中，基于归并的方法十分重要。典型流程是先生成能够装入内存的有序段，将它们写入存储设备，然后把这些有序段归并为更大的有序段。最初的有序段可以用其他排序算法生成；整个过程之所以属于基于归并的方法，是因为其合并阶段采用了归并。(opendsa.cs.vt.edu)

多路归并利用带缓冲的输入，一次合并多个有序段。在有足够内存供缓冲区使用的前提下，增加每轮归并的有序段数量，可以减少遍历全部数据的轮数。在这种场景下，数据在存储设备与内存之间的传输以及访问模式，往往比单纯的处理器操作次数更重要。(opendsa.cs.vt.edu)

并行排序

归并排序也适合并行计算，因为它的两个递归子问题可以独立处理。不过，如果只将递归排序调用并行化，最终的串行归并仍会成为瓶颈。扩展性更好的版本还会将归并工作分配给多个处理器。实际加速效果取决于任务粒度、调度、内存流量和归并的具体实现。(tarjotin.cs.aalto.fi)

记录的稳定排序

当记录需要依次按多个关键字排序时，稳定性非常有用。例如，先按姓名排序，再按部门进行稳定排序，就能在每个部门内部保持姓名顺序。归并排序既能提供这一特性，又能保证最坏情况下的运行时间为 $n\log n$ 量级。(algs4.cs.princeton.edu)

实现中的取舍与优化

与常规快速排序相比，归并排序具有确定的最坏情况时间界限，也较容易实现稳定性，但通常需要更多数组存储空间。堆排序同样保证最坏情况下的运行时间为 $O(n\log n)$ ，并且可以原地运行，但其常规实现并不稳定。这些差异针对的是算法的标准形式；专门设计的变体可能改变其中的某些性质。(algs4.cs.princeton.edu)

常见优化包括：

对较小的子数组使用插入排序。
当左侧部分的最大元素不大于右侧部分的最小元素时，跳过归并。
交替使用输入数组和辅助数组作为源数组与目标数组，以减少复制。

上述边界检查可以使已有序输入的处理时间降为线性，因此，优化后的归并排序不一定仍具有普通实现中 $\Theta(n\log n)$ 的最佳情况时间复杂度。这些改进不会改变标准的最坏情况 $O(n\log n)$ 保证。(algs4.cs.princeton.edu)

历史

归并排序通常被认为是由约翰·冯·诺依曼于 1945 年提出的。它是利用递归分解与归并构建高效计算机排序方法的早期例子，至今仍是算法及其分析研究中的经典内容。(cs.umd.edu)

参考来源

Merge (Algorithms 4/e)algs4.cs.princeton.edu
Mergesortalgs4.cs.princeton.edu
Merge.javaalgs4.cs.princeton.edu
merge — Dictionary of Algorithms and Data Structuresxlinux.nist.gov
Merge Sortcs.umd.edu
A bargain for mergesorts (functional pearl) — How to prove your mergesort correct and stable, almost for freearxiv.org
Sorting Applicationsalgs4.cs.princeton.edu
Strategies for Stable Merge Sortingarxiv.org
tools/lib/list_sort.c — Linux source codekernel.googlesource.com
Simple in-place yet comparison-optimal Mergesortarxiv.org