归并排序详解：原理、代码与时间复杂度

通俗地说，思路是什么

只有零个或一个元素的列表本身就是有序的。对更长的列表：

1. 分：把列表分成左半部分和右半部分。
2. 治：用归并排序分别对每一半排序。
3. 合：合并两个有序的部分。比较各自的第一个元素，把较小的放进输出，重复直到某一半为空；再把另一半剩下的部分复制过来。

真正的工作都发生在合并步骤中，合并总长度为 n 的两个有序列表，最多只需 n − 1 次比较。

逐步演示

对 [38, 27, 43, 3, 9, 82, 10] 排序。

最后一次合并比较队首元素：27 对 3 取 3，27 对 9 取 9，27 对 10 取 10，27 对 82 取 27，38 对 82 取 38，43 对 82 取 43，最后复制 82。七个元素共六次比较。

Python 实现

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # <= takes from left on ties: stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])            # one of these is empty
    out.extend(right[j:])
    return out
def merge_sort(items):
    """Return a new sorted list."""
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort([]))                           # []

这个自顶向下的版本很清晰，但会复制切片。自底向上的版本完全避免了递归：先合并宽度为 1 的段，再合并宽度为 2 的，然后是 4，依此类推。

def merge_sort_bottom_up(items):
    a = list(items)
    width = 1
    while width < len(a):
        for lo in range(0, len(a), 2 * width):
            mid, hi = lo + width, lo + 2 * width
            a[lo:hi] = merge(a[lo:mid], a[mid:hi])
        width *= 2
    return a

自底向上的版本复用了上面的 merge。标准库里还有 heapq.merge，它能惰性地合并任意多个有序的可迭代对象。

时间与空间复杂度

递推式为 T(n) = 2T(n/2) + O(n)。递归树的每一层总共做 O(n) 的工作，约有 log₂ n 层，所以总共是 O(n log n)。对于一百万个元素，大约是 20 层。

归并排序与其他排序算法的比较

归并排序是稳定的，因为遇到相等的元素时，合并会优先取左半部分的，所以相等元素保持原有顺序。与快速排序相比，它的最坏情况有 O(n log n) 的保证，但需要 O(n) 额外内存，并且在数组上通常要搬动更多数据。与堆排序相比，它是稳定的，而且按顺序访问内存，对缓存和磁盘都很友好。

变体与常见错误

• 自然归并排序会检测已经有序的段并合并它们，对有序输入可达 O(n)。Timsort 是改进后的自然归并排序，对短段使用二分插入排序。
• 对小的子列表（例如少于约 10 到 30 个元素）改用插入排序，以减少开销。
• 在链表上，归并排序不需要额外缓冲区：合并只是重新连接节点，所以它是链表排序的常规选择。
• 外部归并排序先对能放进内存的块排序，写入磁盘，再做 k 路归并。数据库以及 GNU sort 等工具对大文件就采用这一思路。
• 统计逆序对：合并时，每当从右半部分取出一个元素，它就比左半部分所有剩余元素都小。

何时使用归并排序

当你需要有 O(n log n) 时间保证的稳定排序、要给链表排序，或者数据太大放不进内存时，就选归并排序。在 Python 中直接调用 sorted() 或 list.sort() 即可：它们实现的是 Timsort，一种归并排序的变体，所以你已经拥有这些特性。手写归并排序是经典的面试题，常延伸到统计逆序对或合并 k 个有序列表。