python - 无法理解 python 的归并排序

Question

我正在研究算法，现在我被困在合并排序代码上。据我了解，mergeSort() 函数采用一个列表并将其划分为一个子列表，直到它的长度小于两个，即只有一个元素并分配给左右变量。之后，它将这些变量传递给 merge() 函数，该函数将左右排序并将其放入新列表并返回此列表。例如，如果输入是 [4,3,2,1]，那么 left=4 right=3，merge(left, right, compare) 将返回 [3,4]，然后我就卡住了。请帮助我理解这个例子。谢谢。

import operator

def merge(left, right, compare):
    result = []
    i,j = 0, 0
    while i < len(left) and j < len(right):
        if compare(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 mergeSort(L, compare = operator.lt):
    if len(L) < 2:
        return L[:]
    else:
        middle = len(L)//2
        left = mergeSort(L[:middle], compare)
        right = mergeSort(L[middle:], compare)
        return merge(left, right, compare) 

标签： pythonalgorithmsortingmergesort