AP CSA Merge Sort 讲义

March 07, 2026

Merge Sort

1. 本节课要搞懂什么

学完这节课，你应该能回答这几个问题：

Merge Sort 到底是在做什么？
它为什么要一直“拆”？
什么时候才真正开始排序？
merge() 到底在干嘛？
程序的真实执行顺序是什么？

2. 先记住一句最重要的话

Merge Sort 往下递归时是在拆分，往上返回时才在排序。

也就是说：

往下：split
往上：merge + sort

很多同学会误以为“拆开以后就已经排好序了”，这是不对的。 拆开只是把问题变小。真正的排序发生在 merge()。

3. 官方代码结构

private static void mergeSortHelper(
    int[] elements, int from, int to, int[] temp)
{
    if (from < to)
    {
        int middle = (from + to) / 2;
        mergeSortHelper(elements, from, middle, temp);
        mergeSortHelper(elements, middle + 1, to, temp);
        merge(elements, from, middle, to, temp);
    }
}

这段代码的结构可以压缩成三句话：

处理左半边
处理右半边
合并左右两边

也就是：

left → right → merge

但是要特别注意：

程序不是看见这三行就平平地一行一行往下走。 它会先一路进入左边的递归，左边整棵子树完成后，才会回来处理右边，最后才做当前层的 merge。

4. base case 是什么

看这一句：

if (from < to)

只有当 from < to 时，程序才会继续拆。

所以 base case 就是：

from == to

意思是： 这一段只剩下 1 个元素了。

而 1 个元素本身就已经有序，所以不需要继续拆，直接返回。

例如：

mergeSortHelper(elements, 3, 3, temp);

这时：

if (3 < 3)   // false

所以方法直接结束并返回。

5. 例子数组

这一节我们统一用下面这组数组来理解：

[2, 8, 5, 3, 9, 4, 1, 7]

下标如下：

 0  1  2  3  4  5  6  7

6. 先分清两个图

学生最容易混淆的是下面这两个东西：

A. 拆分结构图

它告诉你：数组最后会被拆成什么样

B. 程序执行顺序图

它告诉你：程序真正是按什么顺序运行的

这两个不是一回事。聊天记录里最关键的纠正点，就是要让学生知道：

程序不是按层平均展开，而是 depth-first，先左到底。

7. 拆分结构图

如果只看“结构”，数组会被拆成这样：

[2, 8, 5, 3, 9, 4, 1, 7]
├── [2, 8, 5, 3]
│   ├── [2, 8]
│   │   ├── [2]
│   │   └── [8]
│   └── [5, 3]
│       ├── [5]
│       └── [3]
└── [9, 4, 1, 7]
    ├── [9, 4]
    │   ├── [9]
    │   └── [4]
    └── [1, 7]
        ├── [1]
        └── [7]

这只是“最后会拆成这样”的结构图。 不是程序当时真实的运行顺序。

8. 程序真正的执行顺序

程序的真实顺序是这样的：

mergeSortHelper(0, 7)
└── mergeSortHelper(0, 3)
    └── mergeSortHelper(0, 1)
        └── mergeSortHelper(0, 0)   // base case
        └── mergeSortHelper(1, 1)   // base case
        └── merge(0, 0, 1)
    └── mergeSortHelper(2, 3)
        └── mergeSortHelper(2, 2)   // base case
        └── mergeSortHelper(3, 3)   // base case
        └── merge(2, 2, 3)
    └── merge(0, 1, 3)
└── mergeSortHelper(4, 7)
    └── mergeSortHelper(4, 5)
        └── mergeSortHelper(4, 4)   // base case
        └── mergeSortHelper(5, 5)   // base case
        └── merge(4, 4, 5)
    └── mergeSortHelper(6, 7)
        └── mergeSortHelper(6, 6)   // base case
        └── mergeSortHelper(7, 7)   // base case
        └── merge(6, 6, 7)
    └── merge(4, 5, 7)
└── merge(0, 3, 7)

从这里你应该看出它的真实逻辑：

先左到底
再回来
再处理右边
左右都好了
才 merge

这正是 depth-first recursion 的特点。

9. 整个过程怎么变化

用最简洁的形式看整个过程：

开始:
[2,8,5,3,9,4,1,7]

左边先到底:
[2] [8] -> [2,8]
[5] [3] -> [3,5]
[2,8] [3,5] -> [2,3,5,8]

再处理右边:
[9] [4] -> [4,9]
[1] [7] -> [1,7]
[4,9] [1,7] -> [1,4,7,9]

最后:
[2,3,5,8] [1,4,7,9]
-> [1,2,3,4,5,7,8,9]

这个顺序和代码的真实执行顺序是一致的。

10. merge() 到底在做什么

merge() 的任务不是“神秘地把数组排好”。

它只是做一件事：

把两个已经有序的小段，合并成一个更大的有序段。

它的前提一定是：

左边已经有序
右边已经有序

然后程序不断比较左右两边当前最小的元素，谁小就先放进 temp。最后再把结果复制回原数组。

11. merge() 里的三个指针

int i = from;
int j = mid + 1;
int k = from;

作用如下：

i：看左半边
j：看右半边
k：往 temp 里写结果

可以记成：

i 看左
j 看右
k 写结果

12. 例子一：合并 [5] 和 [3]

左边：

[5]

右边：

[3]

比较：

5 和 3

因为 3 更小，所以先放 3，再放 5：

[3, 5]

所以：

[5] [3] -> [3,5]

13. 例子二：合并 [2,8] 和 [3,5]

这是最值得练的一个例子。

左边: [2, 8]
右边: [3, 5]

过程：

比较 2 和 3 -> 放 2
比较 8 和 3 -> 放 3
比较 8 和 5 -> 放 5
右边没了    -> 放剩下的 8

结果：

[2, 3, 5, 8]

14. 最后一次大合并

最后一层会合并这两段：

左边: [2, 3, 5, 8]
右边: [1, 4, 7, 9]

过程如下：

比较 2 和 1 -> 放 1
比较 2 和 4 -> 放 2
比较 3 和 4 -> 放 3
比较 5 和 4 -> 放 4
比较 5 和 7 -> 放 5
比较 8 和 7 -> 放 7
比较 8 和 9 -> 放 8
左边没了    -> 放 9

最后得到：

[1, 2, 3, 4, 5, 7, 8, 9]

这和聊天记录里最后一次 merge 的逐步过程是一致的。

15. 一定要避免的三个错误

错误 1

以为程序会“一层一层整齐地一起拆”。

不对。 程序是先左到底，再回来。

错误 2

以为数组一拆开就已经排好序了。

不对。 拆开只是把问题变小，排序发生在 merge。

错误 3

以为 merge() 只是把两段随便拼起来。

不对。 merge() 的前提是：

左边已经有序
右边已经有序

然后再合成一个更大的有序段。

16. 最后的总结版

把 Merge Sort 的逻辑压缩成最短的版本，就是：

如果这一段只有一个元素，直接 return。
否则分成左右两半。
先递归处理左半边。
再递归处理右半边。
左右都排好后，用 merge() 合并。

再压缩成一句话：

先左到底，再右，到最后 merge。

或者：

往下是拆分，往上是排序。