用python实现计数求逆的错误结果

Question

我正在尝试使用python实现mergeSort的计数版本，下面是我的代码：

def merge(inLeft, inRight):
    inversions = 0; output = []
    while 0 < len(inLeft) and 0 < len(inRight):
        if inLeft[0] < inRight[0]:
            output.append(inLeft[0])
            inLeft.remove(inLeft[0])
        else:
            output.append(inRight[0])
            inRight.remove(inRight[0])
            inversions += len(inLeft)

    if len(inLeft) == 0:
        output.append(inRight[0])
    elif len(inRight) == 0:
        output.append(inLeft[0])    
    return output, inversions

def mergeSort(inList):
    length = len(inList)
    if length == 1:
        return inList, 0
    left, s1 = mergeSort(inList[: length//2])
    right, s2 = mergeSort(inList[length//2: ])
    sortedList, s3 = merge(left, right)
    return sortedList, (s1+s2+s3)

我以为当我通过mergeSort([1, 3, 5, 2, 4, 6])调用它时，我会得到([1, 2, 3, 4, 5, 6], 3)，但实际上我得到了([1, 2, 3, 4], 1)，当我检查它时，我发现left数组总是<built-in function sorted>。你知道吗

我在学习分治算法，因此不擅长用递归分析问题。问题出在哪里？我该怎么修？你知道吗

Answer 1

if len(inLeft) == 0:
    output.append(inRight[0])
elif len(inRight) == 0:
    output.append(inLeft[0])

这只会将第一个元素添加到输出中。更改为output.extend(inRight) / output.extend(inLeft)以有效地添加整个数组。这将修复丢失的元素。你知道吗

此外，Python列表的remove操作具有O(N)复杂性，因此您可能需要考虑使用deque(收藏.deque)，它允许从列表的前面高效地删除。你知道吗