归并排序算法递归疑问：单元素子数组如何与其他部分合并？

代码片段 #

// Sorts the sequence (A[p],...,A[r-1])
template<class T> 
void merge_sort(array<T>& A,int p,int r) 
{ 
  if (p<r-1)     
  { 
     int q=?; // see discussion in the text
     merge_sort(A,p,q);
     merge_sort(A,q,r);
     merge(A,p,q,r);
  }
}

问题背景 #

给定数组[4, 9, 13, 1, 5]，理解归并排序的递归拆分过程：当拆分至单元素子数组[4]时，if(p<r-1)条件不成立，递归分支会被跳过。但疑惑：此时程序如何知晓数组其余部分的位置以执行merge操作？看起来当前仅存在[4]，调用merge(A,p,q,r)时如何获取其他部分进行合并？

核心解答 #

问题的关键在于递归调用的栈结构和上层函数的上下文保存：

• 单个元素的递归调用（比如处理[4]的merge_sort(A,0,1)）并不是孤立的，它是从上层调用（比如处理[4,9]的merge_sort(A,0,2)）中发起的。上层函数在调用子递归前，已经计算好了拆分点q，并且保存了当前的p、r值。
• 当单元素的递归调用执行完毕（直接返回，因为不满足p<r-1），程序会回到上层的递归函数中，继续执行后续代码：先调用另一个子递归（比如处理[9]的merge_sort(A,1,2)），等这个子递归也执行完毕后，上层函数就会调用merge(A,p,q,r)——此时的p、q、r明确指向了需要合并的两个子数组的边界：
  • 比如merge(A,0,1,2)中，A[p..q-1]就是[4]，A[q..r-1]就是[9]，merge操作就是把这两个子数组合并。

结合示例的完整流程（以数组[4,9,13,1,5]为例） #

1. 初始调用merge_sort(A,0,5)，计算q=(0+5)/2=2，先执行merge_sort(A,0,2)。
2. 在merge_sort(A,0,2)中，q=(0+2)/2=1，先调用merge_sort(A,0,1)：因为0 < 1-1不成立，直接返回。
3. 回到merge_sort(A,0,2)，接着调用merge_sort(A,1,2)：同样1 < 2-1不成立，直接返回。
4. 此时merge_sort(A,0,2)执行merge(A,0,1,2)，合并[4]和[9]为[4,9]，然后返回上层。
5. 回到初始调用merge_sort(A,0,5)，接着执行merge_sort(A,2,5)，计算q=(2+5)/2=3，先调用merge_sort(A,2,3)：直接返回。
6. 在merge_sort(A,2,5)中，接着调用merge_sort(A,3,5)，计算q=(3+5)/2=4，先调用merge_sort(A,3,4)：直接返回。
7. 回到merge_sort(A,3,5)，调用merge_sort(A,4,5)：直接返回，然后执行merge(A,3,4,5)，合并[1]和[5]为[1,5]。
8. 回到merge_sort(A,2,5)，执行merge(A,2,3,5)，合并[13]和[1,5]为[1,5,13]，返回上层。
9. 最后初始调用执行merge(A,0,2,5)，合并[4,9]和[1,5,13]，得到最终有序数组[1,4,5,9,13]。

简单来说：单元素的递归调用只是完成了“确认这个子数组已经有序”的工作，真正的合并操作是在它的上层递归函数中执行的，上层函数早已知道要合并的两个子数组的位置信息。

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