归并排序算法的递归

Question

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

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 时，第一个左数组变为 = [4,3] 和右 = [2,1]

现在，当我为左数组递归调用合并排序时，我应该最终得到 left = [4] 之后我为右数组调用它，它应该变为 = [1]

所以，我应该合并 [4] 和 [1]，它应该 return [1,4] 作为最终的排序数组。然而，情况并非如此，代码确实 returns 是正确的排序数组。

编译器解释此递归代码是否有不同的方式？还是我上面写的有误？

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

Answer 1

你的程序是逐行执行的。函数调用暂停当前函数的执行并等待被调用函数return。当一个函数被递归调用时（即使它是间接的，其中 a 调用 b 而 b 调用 a），你基本上得到一个 "new copy" 的函数, 有自己的局部变量和自己的独立执行。在您的示例中，以下是调用顺序。缩进显示该函数正在被外层的函数调用（它将等待它到 return）。请注意 return 不是函数；相反，它停止了它内部的功能。我假设 mergesort 末尾发生的事情是 return 是 merge.

的结果

mergesort([4, 3, 2, 1])
  mergesort([4, 3])
    mergesort([4])
      return [4] to mergesort([4, 3])
    mergesort([3])
      return [3] to mergesort([4, 3])
    merge([4], [3])
      return [3, 4] to mergesort([4, 3])
    return [3, 4] to mergesort([4, 3, 2, 1])
  mergesort([2, 1])
    exercise: figure out the rest :-)

归并排序算法的递归

Recursion of merge sort algorithm

python

recursion

mergesort