理解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)

我得到它正在尝试做的事情,并且我理解合并函数中的所有代码并且对sort函数有基本的了解.

我不明白的是sort函数的"else"部分是如何工作的.它似乎保持递归调用sort函数,为左右变量分配越来越小的拆分列表.但是因为它在每次调用递归函数时都将新列表分配给"左"和"右",所以最终结果不会是左右的最小版本吗？

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

Answer 1

sort()是递归的,但是到了一定程度.if一旦长度list小于2(或等于1),条件将中断递归:

if len(L) < 2:

维基百科实际上有一个很好的动画,显示了Merge排序的工作原理:

基本上,merge()组合两个排序列表并返回单个排序列表.sort()递归地将列表分成对,并一次一步地对这些对进行排序,合并两个已排序的对,以在递归的每一步形成更大的排序列表.只是看动画.解释比我好.