了解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函数，将越来越小的拆分列表分配给左右变量。但是，既然它在每次调用递归函数时都将新列表分配给“左”和“右”，那么最终的结果不就是左和右的最小版本吗？

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

Answer 1

你应该画出调用堆栈，看看会发生什么。

当else子句再次调用sort函数时，该函数不会退出。每个调用都以一个return语句结束。

所以您是正确的，最初对排序的调用是在越来越小的列表中传递的，但是一旦长度小于2，“排序”就会返回列表本身。然后调用返回到它所在的位置并调用print，最后调用合并。

试着用一个小列表记下每个通话。您将看到，最终会在已排序的小列表上调用合并（因为它们很短）。

Answer 2

sort（）是递归的，但在一定程度上是递归的。当列表的长度小于2（或等于1）时，if条件将中断递归：

if len(L) < 2:

维基百科实际上有一个很好的动画，展示了合并排序的工作原理：

基本上，merge（）组合两个排序列表并返回单个排序列表sort（）递归地将列表分成几对，并一步一步地对这些对进行排序，在递归的每一步合并两个排序的对，以形成一个更大的排序列表。只需观看动画。它比我更善于解释。