归并排序递归执行流程疑问：以数组[3,4,2,1,5]为例

针对你提供的归并排序递归实现，处理数组[3,4,2,1,5]时，确实是先执行第1行递归直至触底（子数组长度为1），再执行第2行递归，最后执行当前层的merge操作，所有步骤是依次同步执行的，不存在并行处理的情况。

具体执行流程（假设数组索引从0开始） #

我们可以拆解整个调用栈的执行顺序：

1. 初始调用merge_sort(a, 0, 4)，计算middle=2，优先执行第1行的merge_sort(a, 0, 2)。
2. 进入merge_sort(a, 0, 2)，计算middle=1，继续执行第1行的merge_sort(a, 0, 1)。
3. 进入merge_sort(a, 0, 1)，计算middle=0，执行第1行的merge_sort(a, 0, 0)——此时first等于last，直接返回。
4. 回到merge_sort(a, 0, 1)，开始执行第2行的merge_sort(a, 1, 1)，同样直接返回。
5. 执行当前层的merge(a, 0, 0, 1)，合并子数组[3]和[4]，得到有序的[3,4]。
6. 回到merge_sort(a, 0, 2)，执行第2行的merge_sort(a, 2, 2)，直接返回。
7. 执行当前层的merge(a, 0, 1, 2)，合并[3,4]和[2]，得到有序的[2,3,4]。
8. 回到初始调用merge_sort(a, 0, 4)，现在才开始执行第2行的merge_sort(a, 3, 4)。
9. 进入merge_sort(a, 3, 4)，计算middle=3，执行第1行的merge_sort(a, 3, 3)，返回。
10. 执行第2行的merge_sort(a, 4, 4)，返回。
11. 执行当前层的merge(a, 3, 3, 4)，合并[1]和[5]，得到有序的[1,5]。
12. 回到初始调用，执行最后的merge(a, 0, 2, 4)，合并[2,3,4]和[1,5]，得到最终有序数组[1,2,3,4,5]。

核心逻辑说明 #

递归函数的执行依赖函数调用栈：每次调用子递归时，当前函数的执行会暂停，直到子递归完全执行完毕并返回，才会继续执行当前函数的后续代码。因此第1行的递归必须走完整个分支的所有调用和合并，才会轮到第2行递归，最后才是当前层的merge操作，全程是串行依次执行的。

内容的提问来源于stack exchange，提问作者artur anikin