python - 错误的合并排序

Question

下面是我的合并函数，它应该类似于CLRS中显示的内容第 31 页。现在我已经注释掉了处理任何剩余列表项的代码。

如果我传递 A = [1, 2, 1, 12, 2, 5] 作为输入。输出为 [1, 2, 1, None, None, None]。

有人能告诉我我做错了什么吗？

def Merge(left, right):
    result = [None] * (len(left) + len(right))
    i, j, k = 0, 0, 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result[k] = left[i]
            #result.append(left[i])
            i += 1
        else:
            result[k] = right[j]
            #result.append(right[j])
            j += 1
        k += 1

## remaining items in remaining list
##    while i < len(left):
##        result[k] = left[i]
##        i += 1; k+= 1;
##
##    while j < len(right):
##        result[k] = right[j]
##        j += 1; k+= 1;
##
    return result

## Ref.: CLRS page 34
def MergeSort(A):
    if len(A) > 1:
        mid = int(len(A)/2)
        left = A[:mid]
        right = A[mid:]
        MergeSort(left)
        MergeSort(right)
        return Merge(left, right)
    else:
        return A

if __name__ == "__main__":
    a = [1, 2, 1, 12, 2, 5]
    print "a = %s" % a
    print "sort a = %s" % MergeSort(a)

Answer 1

当调用MergeSort时，您会递归地返回新列表，但永远不会分配它们:

def Merge(left, right):
    result = [None] * (len(left) + len(right))
    i, j, k = 0, 0, 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result[k] = left[i]
            #result.append(left[i])
            i += 1
        else:
            result[k] = right[j]
            #result.append(right[j])
            j += 1
        k += 1

## remaining items in remaining list
##    while i < len(left):
##        result[k] = left[i]
##        i += 1; k+= 1;
##
##    while j < len(right):
##        result[k] = right[j]
##        j += 1; k+= 1;
##
    return result

## Ref.: CLRS page 34
def MergeSort(A):
    if len(A) > 1:
        mid = int(len(A)/2)
        left = A[:mid]
        right = A[mid:]
        #MergeSort(left)
        # here should be
        left = MergeSort(left)
        #MergeSort(right)
        # here should be
        right = MergeSort(right)
        return Merge(left, right)
    else:
        return A

if __name__ == "__main__":
    a = [1, 2, 1, 12, 2, 5]
    print "a = %s" % a
    print "sort a = %s" % MergeSort(a)