python - 理解 Python 中的合并和排序算法

Question

所以我试图在 python 中理解这个简单的合并和排序算法。这是代码:

def merge(left, right, lt):
    """Assumes left and right are sorted lists.

    lt defines an ordering on the elements of the lists.
    Returns a new sorted(by lt) list containing the same elements
    as (left + right) would contain.

    """
    result = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
       if lt(left[i], right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
        while (i < len(left)):
            result.append(left[i])
            i += 1
        while (j < len(right)):
            result.append(right[j])
            j += 1
    return result

def sort(L, lt = lambda x,y: x < y):
    """Returns a new sorted list containing the same elements as L"""
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L)/2)
        left = sort(L[:middle], lt)
        right = sort(L[middle:], lt)
        print left, right
        return merge(left, right, lt)

我明白它要做什么，我理解合并函数中的所有代码，并对排序函数有基本的了解。

我不明白排序函数的“else”部分实际上是如何工作的。好像一直在递归调用sort函数，给左右变量赋值越来越小的分割列表。但是，由于它在每次调用递归函数时都会将新列表分配给“左”和“右”，所以最终结果不会只是左和右的最小版本吗？

似乎位于递归之外的合并函数如何知道它需要合并创建的每个单独的拆分列表？

Answer 1

sort() 是递归的，但在一定程度上。一旦 list 的长度小于二(或等于一)，if 条件将中断递归:

if len(L) < 2:

Wikipedia实际上有一个很好的动画展示了合并排序是如何工作的:

基本上，merge() 合并两个排序列表并返回一个排序 列表。 sort() 递归地将您的列表分解成对，并一次一步对这些对进行排序，在递归的每一步合并两个排序对以形成更大的排序列表。看动画就好了。它比我更擅长解释。