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

Question

我想知道这个递归算法的流程是如何工作的：an inversion counter based on merge-sort。当我查看合并排序递归树的图表时，它似乎相当清晰；我以为叶子会一直分裂，直到每片叶子都是一个单元，然后 merge() 会开始组合它们；因此，启动 'moving back up' 树 -- 可以这么说。

但是在下面的代码中，如果我们用给定的数组 print(sortAndCount(test_case)) 打印出这个函数，那么我们实际上是从 merge() 函数得到我们的 'final' 输出，而不是return sortAndCount() 中的语句？所以在下面的代码中，我认为 sortAndCount() 方法会在 (invCountA, A) = sortAndCount(anArray[:halfN]) 中一遍又一遍地调用自己，直到达到基本情况，然后继续处理数组的下半部分——但现在似乎不正确。有人可以纠正我对这种递归流程的理解吗？（N.b。我截断了 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 创建的下图显示了递归调用的顺序，如文档中所述 边按 [=20= 遍历它们的顺序编号] 边缘从黑色到灰色着色以指示遍历顺序：首先是黑色边缘，最后是灰色边缘。:

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

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

Understanding the recursion in mergesort-like algorithms

python

algorithm

recursion

mergesort