在 python 的归并排序中使用递归

Question

我在python学习归并排序，对下面程序的实现有点迷茫。按照我的理解，在实现mergeSort ([3,1], compare)的时候，分裂成了mergeSort([3], compare)和mergeSort([1], compare)。然后 merge([3],[1], compare) 应该被调用，因此 print 语句应该是 left = [1,3]，但程序实际上打印出 left = [3,1]，其他 print 语句也是如此，为什么？非常感谢。

def merge(left, right, compare):
    """Assumes left and right are sorted lists and compare defines an ordering
       on the elements.
       Returns a new sorted (by compare list containing the same elements as
       (left + right) would contain."""
    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

import operator

def mergeSort(L, compare = operator.lt):
    """Assumes L is a list, compare defines an ordering on elements of L
       Returns a new sorted list containing the same elements as L"""
    if len(L) < 2:
        return L[:]
    else:
        middle = len(L)//2
        print "middle =", middle
        left = mergeSort(L[:middle], compare)
        print "left = ", L[:middle]
        right = mergeSort(L[middle:], compare)
        print "right = ", L[middle:]
        return merge(left, right, compare)

>>> L = [3,1,2,5,4,9,6,7,8]
>>> mergeSort(L, compare = operator.lt)
middle = 4
middle = 2
middle = 1
left =  [3]
right =  [1]
left =  [3, 1]
middle = 1
left =  [2]
right =  [5]
right =  [2, 5]
left =  [3, 1, 2, 5]
middle = 2
middle = 1
left =  [4]
right =  [9]
left =  [4, 9]
middle = 1
left =  [6]
middle = 1
left =  [7]
right =  [8]
right =  [7, 8]
right =  [6, 7, 8]
right =  [4, 9, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer 1

此代码打印 L，因为它被递归拆分。它实际上并不打印任何合并的结果。您可以通过更改行

来查看每次合并的结果

return merge(left, right, compare)

至

merged = merge(left, right, compare)
print "merged = ", merged
return merged

Answer 2

这是问题所在：

    print "left = ", L[:middle] # content of L before sorting

将此行和其他类似的 print 语句替换为：

    print "left = ", left # actual result of mergeSort

Answer 3

left = mergeSort(L[:middle], compare)
print "left = ", left
right = mergeSort(L[middle:], compare)
print "right = ", right

这应该有效。

在 python 的归并排序中使用递归

The use of recursion in merge sort for python

python

recursion

mergesort