合并排序递归如何工作（基于 1 个索引）

Question

假设我们有 8 个长度的数组（假设第一个索引是 1 以便更好地表示）。

在第一次递归 mergesort(1,8) 中压入堆栈， 第二次递归 mergesort(1,4) 压入堆栈， 第三次递归 (1,2) 压入堆栈， 第 4 次调用 (1,1) 压入堆栈（'因为 l 仍然低于 h）。

堆栈是 [(1,8),(1,4),(1,2),(1,1)]

在这一步之后我很困惑，我无法理解递归是如何在这个 1,1 从堆栈中展开的，我们是 '?'在第 3 步（1,2）中，我们是要调用 mergesort（mid+1，h）还是要再次从堆栈中展开 1,4？ 希望不会因为这个我理解合并排序如何工作的一般表示但是当我尝试更深入时我失败了..（也很感激为什么用一些解释来贬低..）

Answer 1

你要像你说的那样调用 Mergesort(mid+1, h)。请记住，伪代码的形式为：

Mergesort(array, low,  high){
  if(low < high){
    mid = (low + high) / 2; // We will ignore overflows, don't @ me
    Mergesort(array, low, mid);
    Mergesort(array, mid+1, high);
    Merge(array, low, high);
  }
}

所以堆栈会像你拥有的那样展开：

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

这是因为首先，对 Mergesort(low, mid) 的递归调用正在下降，直到 if 语句找到一个已经排序的范围。然后，堆栈展开一个级别到第一次调用 Mergesort(mid+1, high)。当递归调用终止时，执行将从该调用停止的地方继续。最终，当最后一步合并两半时，整个数组将被排序。