归并排序递归调用的栈结构及merge执行顺序解析

一、递归栈的形成过程 #

归并排序的mergeSort函数采用深度优先递归：先一直拆分左半部分数组，直到子数组只剩一个元素（left == right，递归终止），再回溯处理右半部分，最后合并左右。以下是针对目标数组的栈动态变化：

• 第一步：调用mergeSort(arr, 0, 6)，函数帧压入栈，待处理整个数组[5,4,6,7,8,2,1]。
• 第二步：拆分左半部分，调用mergeSort(arr, 0, 3)，函数帧压入栈，待处理子数组[5,4,6,7]。
• 第三步：继续拆左半，调用mergeSort(arr, 0, 1)，函数帧压入栈，待处理子数组[5,4]。
• 第四步：拆到最小单元，调用mergeSort(arr, 0, 0)，函数帧压入栈；此时left == right，递归终止，弹出该函数帧。
• 第五步：处理mergeSort(arr,0,1)的右半部分，调用mergeSort(arr, 1, 1)，函数帧压入栈；递归终止，弹出该函数帧。
• 第六步：栈顶现在是mergeSort(arr,0,1)，执行merge(arr,0,0,1)，合并完成后弹出该函数帧。
• 第七步：回到栈顶mergeSort(arr,0,3)，处理右半部分，调用mergeSort(arr, 2, 3)，函数帧压入栈，待处理子数组[6,7]。
• 第八步：拆左半，调用mergeSort(arr,2,2)，函数帧压入栈；递归终止，弹出。
• 第九步：处理右半，调用mergeSort(arr,3,3)，函数帧压入栈；递归终止，弹出。
• 第十步：栈顶是mergeSort(arr,2,3)，执行merge(arr,2,2,3)，合并完成后弹出该函数帧。
• 第十一步：栈顶回到mergeSort(arr,0,3)，执行merge(arr,0,1,3)，合并完成后弹出该函数帧。
• 第十二步：回到初始的mergeSort(arr,0,6)，处理右半部分，调用mergeSort(arr,4,6)，函数帧压入栈，待处理子数组[8,2,1]。
• 第十三步：拆左半，调用mergeSort(arr,4,5)，函数帧压入栈，待处理子数组[8,2]。
• 第十四步：拆到最小单元，调用mergeSort(arr,4,4)，函数帧压入栈；递归终止，弹出。
• 第十五步：处理右半，调用mergeSort(arr,5,5)，函数帧压入栈；递归终止，弹出。
• 第十六步：栈顶是mergeSort(arr,4,5)，执行merge(arr,4,4,5)，合并完成后弹出该函数帧。
• 第十七步：回到mergeSort(arr,4,6)，处理右半部分，调用mergeSort(arr,6,6)，函数帧压入栈；递归终止，弹出。
• 第十八步：栈顶是mergeSort(arr,4,6)，执行merge(arr,4,5,6)，合并完成后弹出该函数帧。
• 第十九步：回到初始调用mergeSort(arr,0,6)，执行merge(arr,0,3,6)，合并完成后弹出该函数帧，整个排序结束。

二、merge函数的调用顺序 #

merge函数只有在左右子数组都完成排序后才会触发，调用顺序完全跟着递归回溯的节奏走，具体执行顺序和作用如下：

1. merge(arr, 0, 0, 1)：合并单个元素的子数组[5]和[4]，得到有序子数组[4,5]
2. merge(arr, 2, 2, 3)：合并[6]和[7]，得到[6,7]
3. merge(arr, 0, 1, 3)：合并[4,5]和[6,7]，得到[4,5,6,7]
4. merge(arr, 4, 4, 5)：合并[8]和[2]，得到[2,8]
5. merge(arr, 4, 5, 6)：合并[2,8]和[1]，得到[1,2,8]
6. merge(arr, 0, 3, 6)：合并[4,5,6,7]和[1,2,8]，得到最终有序数组[1,2,4,5,6,7,8]

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