python-3.x - 合并函数如何调用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()

标签： python-3.xalgorithmsortingmergesort

Answer 1

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

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

仅merge_sort()递归调用自身，将其列表参数拆分为左右部分，直到它减少为单个元素。每组递归调用之后是一个合并阶段，其中排序的子列表被合并到一个返回给其调用者的排序子列表中......