归并排序

题目描述

分：对半切到只剩单个元素(天然有序)。合：把相邻的两个有序段合并成更大的有序段，直到合成整个数组。

思路解析

两个有序段各放一个指针，比较两个指针处的值，小的放进结果、该指针前进，直到一段取完，另一段剩余直接接上——和合并两个有序链表一模一样。

对半切分：先把数组切成左半 [5,2,8] 和右半 [1,9,3]，各自再递归切分、排序。

两半各自排好：递归到底再合并，左半排成 [2,5,8]、右半排成 [1,3,9]。现在合并这两个有序段。

合并 · 比 2 和 1 → 取 1：左指针指 2、右指针指 1：1 更小，先取 1。结果：[1]。右指针前进到 3。

比 2 和 3 → 取 2，再取 3：比 2 和 3：取 2；再比 5 和 3：取 3。结果累积：[1,2,3]。谁小取谁，指针各自前进。

合并完成：继续比 5、8 和 9，依次取出，合并成 [1,2,3,5,8,9]。整个数组有序。

归并是“分治”的标准范本：把大问题对半拆、解决子问题、再合并。“合并两个有序”这个子过程(21 题)是它的核心积木，也用于求逆序对。

参考代码（Python）

1def merge_sort(a):
2    if len(a) <= 1: return a            # 单个天然有序
3    mid = len(a) // 2
4    L = merge_sort(a[:mid])            # 分 + 递归排左
5    R = merge_sort(a[mid:])           # 分 + 递归排右
6    res, i, j = [], 0, 0
7    while i < len(L) and j < len(R):   # 合并：谁小取谁
8        if L[i] <= R[j]: res.append(L[i]); i += 1
9        else: res.append(R[j]); j += 1
10    return res + L[i:] + R[j:]         # 接上剩余

复杂度分析

• 时间复杂度：O(n log n) —— 稳定保证，与输入无关
• 空间复杂度：O(n) —— 合并需要额外数组

套路模板

记住骨架：双指针谁小取谁、相等取左保稳定、最后接残段。这个“合并有序”是归并排序、求逆序对、合并K个有序的共同内核。

1i = j = 0; res = []
2while i < len(L) and j < len(R):
3    if L[i] <= R[j]: res.append(L[i]); i += 1   # 等时取左=稳定
4    else: res.append(R[j]); j += 1
5res += L[i:] + R[j:]                  # 接残段

易错点

• ❌ 相等时取右 → ✅ 相等取左 L[i] <= R[j]（取左才稳定(相等元素相对顺序不变)）
• ❌ 忘了接剩余段 → ✅ res + L[i:] + R[j:]（一段取完后另一段剩余要补上）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。