merge函数是如何调用merge_sort函数的？

Question

def merge_sort(items):
  if len(items) <= 1:
    return items

  middle_index = len(items) // 2
  left_split = items[:middle_index]
  right_split = items[middle_index:]

  left_sorted = merge_sort(left_split)
  right_sorted = merge_sort(right_split)

  return merge(left_sorted, right_sorted)

def merge(left, right):
  result = []

  while (left and right):
    if left[0] < right[0]:
      result.append(left[0])
      left.pop(0)
    else:
      result.append(right[0])
      right.pop(0)

  if left:
    result += left
  if right:
    result += right

  return result

unordered_list1 = [356, 746, 264, 569, 949, 895, 125, 455]

ordered_list1 = merge_sort(unordered_list1)

我知道当函数merge_sort()第一次被调用时，它会递归地调用自己，直到只剩下一个元素，然后在返回时再次调用merge()函数，该函数将返回一个有序的子列表，但是然后函数merge_sort()如何调用自己来移动到下一个元素呢？我尝试可视化代码，但当return merge(left_sorted, right_sorted)语句再次转到run merge_sort()时遇到了问题。

谁能解释一下在第一次返回一个有序的子列表后，return merge(left_sorted, right_sorted)是如何再次调用merge_sort()的。

Answer 1

谁能解释一下return merge(left_sorted，right_sorted)是如何在第一次返回有序的子列表之后再次调用merge_sort()的。

因为调用merge_sort()的前一个实例仍在堆栈上。使用缩进来显示调用的嵌套，以4个元素为例：

ordered_list = call merge_sort(items{0 .. 3})
    left_sorted  = call merge_sort(left_split = items{0..2})
        left_sorted  = call merge_sort(left_split  = items{0}) // base case
        right_sorted = call merge_sort(right_split = items{1}) // base case
        return merge(left_sorted, right sorted)
    right_sorted = call merge_sort (right_split = items{2..3})
        left_sorted  = call merge_sort(left_split  = items{2}) // base case
        right_sorted = call merge_sort(right_split = items{3}) // base case
        return merge(left_sorted, right sorted)
    return merge(left_sorted, right sorted)

Answer 2

可以解释一下，在第一次返回一个有序的子列表之后，return merge(left_sorted, right_sorted)是如何再次调用merge_sort()的吗？

merge不调用merge_sort()，它将两个已排序的子列表合并到一个已排序的列表中。

只有merge_sort()递归地调用它自己，将它的列表参数分成左右两部分，直到它被简化为单个元素。每组递归调用之后都有一个合并阶段，在该阶段中，已排序的子列表将合并到一个已排序的子列表中，并返回给其调用者...