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)语句再次运行到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

有人能解释一下returnmerge(left_sorted, right_sorted)是如何在第一次返回有序子列表后再次调用merge_sort()的吗。

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

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