合并排序算法是如何“爬上树”的？

Question

我很难理解递归合并排序算法是如何工作的，理论上我理解它是如何工作的:如果数组中有多个元素，找到它的中间元素，并将数组划分为两个较小的子数组，等等，直到有两个数组，按照定义已经被排序(基本情况)，那么您可以使用合并算法合并它们，然后沿着树向上移动等等。

我尝试在python中用几个print语句一步一步地来实现它，而且它可以工作，但是我真的不明白为什么它会以这样的方式工作。我会描述我的错误逻辑：

以l为低索引，h为高索引的伪码算法：

merge_sort(l,h){

if(l < h){
mid = (l+h)//2
merge_sort(l,mid) 
merge_sort(mid+1,h)
merge(l,mid,h)
}

}

所以对于arr = 9,3,7,5

• 我们称merge_sort(0,3)为全数组，l=0，h =3，mid =1.9，3，7，5
• l
• l

从这里开始，，l，==，h，所以我们不满足条件l(这显然是错误的)，但是在这里，它上升并调用merge_sort(1,1) 3，然后执行合并。在此之后，它再次上升，处理初始数组merge_sort(2,3) 7,5的右侧，并继续进行。(7然后5然后合并)

有谁能解释一下为什么算法会在l == n之后继续自称？我读过一些解释，看过一些视频，有的甚至争论合并(l，mid)将完整的前半部分9,3排序，合并(mid+1，h)排序后半部分7,5，这显然不是它的工作方式，我真的很困惑。

Answer 1

它不再调用自己，它返回到递归的前一步，一旦它完成了当前的步骤。

下面是一个合并排序算法的GeeksForGeeks示例，每个步骤都按顺序进行数字标记：

​

Answer 2

您可以通过信任递归算法来理解它。请看下面的注释(!启动注释)：

merge_sort(l,h) {

if (l < h) {
    mid = (l+h)//2
    merge_sort(l,mid) ! If merge_sort does its job, the array is now sorted from l to mid
    merge_sort(mid+1,h) ! If merge_sort does its job, the array is now sorted from mid+1 to h
    merge(l,mid,h) ! If merge does its job, the array is now sorted from l to h
}
else { ! If l==h, the array is already sorted from l to h
}

现在您可以看到，如果我们用l和h的一些值调用函数，它将返回一个排序数组，方法是在数组的一部分上调用自己，每次都返回排序的数组。整个构造之所以有效，是因为子数组的大小随着调用级别的减少而减小，并且始终达到1，从而立即返回到调用级别。