归并排序为什么稳：分治 + 合并的 O(n log n)

图：归并排序的"分—治—合"——稳定来自合并时不越位

归并排序的递推式 $T(n)=2T(n/2)+\Theta(n)$ 是主定理情况2的"标准示范"：拆分到单元素，再自底向上把两个有序段合并。合并时一次线性扫描，保证整体 $\Theta(n\log n)$。

稳定从哪来

合并两个有序段时，遇到相等元素，先取"前半段"的，后半段的元素就不会越过它——这就是稳定性的来源。快排因为有"跨区交换"，一般不保稳定；归并天然稳定，因此适合"多关键字排序"（先按工资、再按部门，稳定排序能保住工资序）。

参考代码：合并两个有序段

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:       # 相等时取左，保证稳定
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

def mergesort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    return merge(mergesort(a[:mid]), mergesort(a[mid:]))   # T(n)=2T(n/2)+Θ(n)

print(mergesort([5, 2, 4, 6, 1, 3]))   # [1, 2, 3, 4, 5, 6]

代价是额外 $O(n)$ 空间（不像快排原地），但换来"最坏也 $\Theta(n\log n)$ + 稳定"的双重保障，所以 Python 的 Timsort 也以归并为底。

关联推荐

• 插入、选择、冒泡排序（KU） — 看 O(n²) 与归并 O(n log n) 的对比
• 算法通关训练营·排序篇（课程） — 系统学完所有排序
• 从冒泡到快排 — 为什么工程里归并与快排各有地盘