python - 了解类归并排序算法中的递归

Question

我想知道这个递归算法的流程是如何工作的:an inversion counter based on merge-sort 。当我查看合并排序递归树的图表时，它看起来相当清晰；我认为叶子会不断 split ，直到每个叶子成为一个单元，然后 merge() 就会开始将它们组合起来；因此，开始在树上“向上移动”——可以这么说。

但是在下面的代码中，如果我们使用给定的数组打印出这个函数 print(sortAndCount(test_case)) 那么我们实际上是从 merge 中获得“最终”输出() 函数，而不是 sortAndCount() 中的 return 语句？因此，在下面的代码中，我认为 sortAndCount() 方法会在 (invCountA, A) = sortAndCount(anArray[:halfN]) 中一遍又一遍地调用自身，直到到达基本情况，然后继续处理数组的下半部分——但现在看来这是不正确的。有人可以纠正我对这个递归流程的理解吗？ (注意，我截断了 merge() 方法的一些代码，因为我只对递归过程感兴趣。)

def sortAndCount(anArray):
    N = len(anArray)
    halfN = N // 2

    #base case:
    if N == 1: return (0, anArray)          

    (invCountA, A) = sortAndCount(anArray[:halfN])
    (invCountB, B) = sortAndCount(anArray[halfN:])
    (invCountCross, anArray) = merge(A, B)

    return (invCountA + invCountB + invCountCross, anArray)

def merge(listA, listB):
    counter = 0
    i, j = 0, 0

    #some additional code...
    #...
    #...


    #If all items in one array have been selected, 
    #we just return remaining values from other array:
    if (i == Asize):                                
        return (counter, output_array + listB[j:])
    else:
        return (counter, output_array + listA[i:])

Answer 1

以下图像使用 rcviz 创建显示递归调用的顺序，如文档中所述边缘按执行遍历的顺序进行编号。边缘的颜色从黑色到灰色以指示遍历顺序:黑色边缘优先，灰色边缘最后。:

因此，如果我们仔细遵循这些步骤，我们会发现我们首先完全遍历原始数组的左半部分，然后是右半部分。