归并排序两步：先分到只剩一个，再两两合回去。 合的时候只比两个队头，谁小拿谁——所以合并一遍是线性的。 总步数是 n 乘 log2(n)。八个数看不出优势，一百万个能差两万多倍。
前面三个排序都在「怎么换」上下功夫，归并换了个思路：先把它拆小。 这是全书第一次出现「分治」——先分成小问题，解决完再合起来。第 7 章的递归会回到这里。 这一篇的重点不是代码，是为什么分一下就能变快。
一、先看归并这一步
两个已经排好的队列：2 4 5 8 和 1 3 6 7。要合成一个有序的。
做法极简单：只看两个队头，谁小拿谁。
1 比 2 小，拿 1；现在左边队头是 2，2 比 3 小，拿 2；再比 3 和 4，拿 3……
演示里七次取数，最后得到 1 2 3 4 5 6 7 8。
关键在于：取过的数永远不用回头看。因为两队各自有序，拿走的那个一定是当前最小的。
所以合并一遍只要走一趟，是线性的。这是归并排序能快的全部秘密。
二、分到不能再分，再合回去
八个数的做法：先分成两半，各四个；再各分成两半，各两个；再各分成两半，各一个。 一个元素的数组天生有序——所以分到这一步，就不用再分了。 然后往回走：两个一个的合成两个，两个两个的合成四个，两个四个的合成八个。
每一步合并都只是「比队头、谁小拿谁」，所以每一步都是线性的。 演示里那张层数表就是这个过程：第 0 层 1 段长 8，第 1 层 2 段长 4，第 2 层 4 段长 2， 第 3 层 8 段长 1。 八个数分 3 层到底，因为 8 是 2 的 3 次方。
三、n log n 是怎么来的
层数是 log2(n)：8 个数 3 层，1024 个数 10 层，一百万个约 20 层。 每一层合并一共要比 n 次左右（每个元素都要被取一次）。 所以总步数是 n 乘 log2(n)。 八个数是 8 乘 3 得 24 的量级，实测合并比了 17 次——比 24 少，因为有些比较提前定了胜负。
这就是 O(n log n)：n 是一次，log n 是层数。数据翻倍，多一层，总步数差不多翻倍多一点。 对比一下 O(n²)：数据翻倍，步数翻四倍。翻几次就差出天际了。 八个数时归并 17 次、选择排序 28 次，差别不大。小数据上看不出好算法好在哪，这是常态。
四、数据大了才见真章
一百万个数据：选择排序要 100 万乘 100 万除 2，五千亿次。 归并排序要 100 万乘 20，两千万次。 差两万多倍。 五千亿次按每秒十亿次算也要五千秒，两千万次是零点零二秒。
注意这两个数是「按公式算出来的」，不是跑出来的——大数据的差距在纸上就能算清。 这也是为什么算法分析值得学：不用真跑，就能知道哪个方案会崩。等真跑出来才知道，往往已经晚了。
五、代价：多占一份内存
归并要靠一个临时数组装合并结果，所以要额外 n 个位置。 数据大到内存装不下时，这就是硬伤——它没法「就地」完成。 有意思的是，正因为这个特点，它反而成了「排超大文件」的首选：一次只合并两块，不需要全塞进内存。
这种做法叫外部排序。 一个缺点在另一个场景里正好是优点——这在本课不是第一次出现了（第 3 章的链表也是）。 所以归并的定位很清楚：要快、要稳定、内存够，就用它。内存紧，就得换别的。
六、动手 Demo：先把8个数分到底，再一层层合回来
先看两个有序队列怎么合成一个：只比队头，谁小拿谁。 再把八个数递归地分到只剩一个，然后逐层合回去，数一数一共比了几次。 最后把层数打出来，对照 log2(8) = 3。
def merge(left, right):
out, i, j, cnt = [], 0, 0, 0
while i < len(left) and j < len(right):
cnt += 1
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:])
out.extend(right[j:])
return out, cnt
def msort(a, depth=0):
if len(a) <= 1:
return a, 0
mid = len(a) // 2
L, c1 = msort(a[:mid], depth + 1)
R, c2 = msort(a[mid:], depth + 1)
out, c3 = merge(L, R)
print(' ' * depth, out)
return out, c1 + c2 + c3
a = [5, 3, 8, 4, 2, 7, 1, 6]
res, total = msort(a)
print(res, '一共比了', total, '次')
实跑输出：
--------------------------------------------------------------------
归并排序：先分到不能再分，再合回去
--------------------------------------------------------------------
① 先看「归并」这一步
--------------------------------------------------------------------
两个已经排好的队列：[2, 4, 5, 8] 和 [1, 3, 6, 7]
取 1（右边）
取 2（左边）
取 3（右边）
取 4（左边）
取 5（左边）
取 6（右边）
取 7（右边）
合起来：[1, 2, 3, 4, 5, 6, 7, 8]
两个队列各自有序，只需要比队头。谁小拿谁，拿完再比。
这样比一遍就够，不用回头——所以归并一次合并是线性的。
② 再把它用到整批数据上
--------------------------------------------------------------------
8 个数：[5, 3, 8, 4, 2, 7, 1, 6]
分到底再合回来：[1, 2, 3, 4, 5, 6, 7, 8]
合并时一共比了 17 次
| 层 | 分成几段 | 每段多长 |
|---|---:|---:|
| 第 0 层 | 1 | 8 |
| 第 1 层 | 2 | 4 |
| 第 2 层 | 4 | 2 |
| 第 3 层 | 8 | 1 |
8 个数分 3 层到底，因为 8 是 2 的 3 次方。
每层合并总共要比 n 次左右，所以总步数是 n 乘 log2(n)——8 × 3 = 24 量级。
对比选择排序的 28 次，8 个数时差别不大。
但 100 万个数时：选择排序要 5000 亿次，归并只要 2000 万次——差 2 万倍。
这就是 O(n log n) 和 O(n²) 的区别。
③ 代价是多占一份内存
--------------------------------------------------------------------
归并要靠一个临时数组来装合并结果，所以要额外 n 个位置。
数据大到内存装不下时，这就是硬伤——不过也正因为这样，外部排序（磁盘上排序大文件）用的就是归并：
一次只合并两块，不需要全塞进内存。
①merge 的 cnt 只数「两个队头比大小」的次数，不包括后面的收尾复制。
这就是第 5.1 说的「比较次数」这个指标。
②<= 而不是 <，这一处决定了归并是稳定的：两个相等的数，左边的先进来，保持原来的先后。
③msort 先递归分左右，再合并，最后打印。所以输出是从最短的段开始，一层层变长。
④' ' * depth 是缩进，看得出层数。八个数最后三层缩进，正好对上 log2(8) = 3。
30 秒实验
- 把
<=改成<，想想稳定性会不会变（同分的两个数谁先进）。 - 把数据换成 16 个数，看层数变成几层，验证「翻倍多一层」。
- 只跑
merge([2, 4, 5, 8], [1, 3, 6, 7])，数一下比了几次。
常见误区
- 「归并排序是把数组分成两半各排一遍。」分完还要合，合才是关键那一步。
- 「n log n 就是 n 乘 n。」log2(n) 是层数，不是 n。一百万个数据是 20 层，不是一百万层。
- 「归并排序处处比别的强。」要多占 n 个位置，内存紧的时候用不了。
自测三问（点开对答案）
1. 归并的「合」为什么是线性的？ —— 两个队列各自有序，只比队头，谁小拿谁，取走的不回头。走一趟就够。 2. 八个数为什么要分 3 层？ —— 每分一次对半，8 到 4 到 2 到 1，正好 3 次。因为 8 是 2 的 3 次方。 3. 归并排序的额外内存是多少？ —— n 个位置（临时数组）。所以它没法就地排序。归并靠「分」变快。 下一节还有两个狠角色：一个把插入排序改成「先粗排再细排」， 一个挑个基准把数据分两边——后者是公认最快的那一类。
- ☐ （本篇完，下一篇 5.5 希尔排序与快速排序）