合并排序算法的递归

Question

几天前我开始学习python，当时我正试图解决排序算法。我最近开始使用合并排序算法。 python中的一个典型的合并排序程序（据我所知）包括一个合并函数和一个mergesort函数。在我见过的所有程序中，以下几行都很常见：

left = mergesort(left)
right = mergesort(right)
merge(left, right)

例如此代码：

def divide_arr(a):    #same as mergesort function
    l = len(a)
    if l <= 1: return a
    left = a[0:int(l/2)]
    right = a[int(l/2):l]
    left = divide_arr(left)
    right = divide_arr(right)
    return merge(left, right, a)

def merge(left, right, arr):
    pl, pr, pa = 0, 0, 0
    while pl <len(left) and pr < len(right):
        if left[pl] <= right[pr]:
            arr[pa] = left[pl]
            pa += 1
            pl += 1
        elif left[pl] > right[pr]:
            arr[pa] = right[pr]
            pa += 1
            pr += 1
    while pl < len(left):
        arr[pa] = left[pl]
        pa += 1
        pl += 1
    while pr < len(right):
        arr[pa] = right[pr]
        pa += 1
        pr += 1
    return arr

我真的不确定编译器如何解释这些行。

让我们接受一个数组[4,3,2,1]。因此，当我调用mergesort时，第一个Left数组变为= [4,3]，而right = [2,1]

现在，当我递归地为左数组调用mergesort时，我应该最终得到left = [4]，然后，我为应为= [1]的right数组调用它。

所以，我应该将[4]和[1]合并，并且它应该返回[1,4]作为最终排序的数组。但是，事实并非如此，并且代码确实返回了正确的排序数组。

编译器解释递归代码的方式是否不同？还是我上面写的东西错了？

PS：我知道这里已经回答了类似的问题，但是它们不处理代码的这些特定行，而是提供合并排序的一般概念

几天前我开始学习python，当时我正试图解决排序算法。我最近开始使用合并排序算法。 python中一个典型的合并排序程序（据我所知）包括...

Answer 1

您的程序逐行执行。函数调用会暂停当前函数的执行，并等待被调用函数返回。当递归调用函数时（即使是间接调用，a调用b，b调用a），则基本上可以获得该函数的“新副本”，它具有自己的局部变量和自己的独立执行。在您的示例中，以下是调用的顺序。缩进显示该函数在外部级别被函数调用（它将等待其返回）。请注意，return不是函数。相反，它将停止其内部的功能。我假设在mergesort末尾发生的事情是它返回了merge的结果。