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

Question

我很难理解递归合并排序算法是如何工作的，我理解它在理论上是如何工作的：如果一个数组中有多个元素，找到它的中间，将数组分成两个较小的子数组，依此类推，直到你有两个1个元素的数组，根据定义已经排序（基本情况），然后你可以使用合并算法合并它们，然后你爬上树，依此类推。

我试着用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， mid1[9,3,7,5]
• l

从这里l==h，我们不满足条件l

有人能解释一下为什么算法在l==n之后继续称自己吗？我读了一些解释，看了一些视频，有些人甚至认为merge（l，mid）排序完整的上半部分[9,3]，merge（mid 1，h）排序完整的下半部分[7,5]，这显然不是它的工作原理，我真的很困惑。

Answer 1

通过信任递归算法，您可以理解它。请看下面的注释（！开始注释）：

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，从而立即返回到调用级别。

Answer 2

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