合并排序递归版本背后的直觉

Question

我在书中找到了以下部分归并排序程序：

def sort(v):
    if len(v)<=1:
       return v
    mid=len(v)//2
    v1,v2=sort(v[:mid]),sort(v[mid:])
    return merge(v1,v2)

merge 的作用是比较 v1 和 v2 的每个元素，并在必要时在它们之间进行交换。我的问题与 sort() 函数有关。例如，如果我传递一个列表，如：[5,2,4,8,6,3]。它将被分成块，递归地调用 sort() 函数，但我不知道它在哪一点调用 merge() 函数。那么，如果我假设下半部分执行的调用集如下所示，可以吗：

sort([5,4,2])=v1        sort([8,6,3])=v2

(at this point is called merge(v1,v2) or does it wait to the list to be exhausted?)

sort([5])=v1 sort ([4,2])=v2

(because the length of v1 is less than 1 then returns v which is [5], in this part I do not know how it gets joined with v2)

v[5]     sort(v[4])=v1  sort(v[2]))
(v[5] has been returned and the right part gets ordered so we will have v=[2,4])

在最后一部分中，我只是不知道是否应该使用 v[5] 和 v=[2,4] 调用 merge 来进行排序，是这样的吗？或者我错过了什么？

我怎样才能正确解释这个源代码？

Answer 1

为了演示合并排序的工作原理，我展示了我不久前编写的自己的实现：

def mergesort(lst):
    # SORT PART ------------------------------------------------
    # base case: return just this list if length = 1
    if len(lst) <= 1:
        return lst
    # recursive case: do mergesort() on either half of the list
    mid = len(lst) // 2
    sub1, sub2 = mergesort(lst[:mid]), mergesort(lst[mid:])

    # MERGE PART ------------------------------------------------
    # merge sub1 and sub2, which are each sorted
    sorted_lst = []
    while sub1 and sub2:  # ...are not empty...
        # remove the lesser element from the front of sub1 or sub2 and add it to sorted list
        sorted_lst.append(sub1.pop(0) if sub1[0] < sub2[0] else sub2.pop(0))
    # finally, once one of the lists are empty, append the remainder of the other list.
    sorted_lst += (sub1 if sub1 else sub2)
    # and return the now-sorted list
    return sorted_lst

本质上，合并排序会重复地将列表分成两半，直到它到达单例列表。此时它将较低的元素放在较高的元素之前并返回该元素。

然后，上一级考虑它返回的两个列表，并将它们都视为优先级队列 - 删除它们之间的最低元素，然后删除它们之间的下一个最低元素，依此类推。所述最低元素始终位于前面，因为较低的递归层就是这样的。

Answer 2

在自上而下的合并排序中，直到发生子数组大小已减少为单个元素的两个基本情况时，合并才会开始。之后，合并和拆分继续在调用链中上下移动，深度优先，通常先离开。

使用问题示例代码，递归将重复遵循 sort(v[:mid]) 的左侧路径，直到在该实例返回之前到达基本情况一个元素，以允许第二次调用 sort(v[mid:])，这可能是两个元素，在这种情况下会发生另一级递归，然后开始合并。