使用归并排序计算逆序数 Python

Question

我正在实现一个归并排序，并且要计算逆序对的数量。我的代码在处理小文件（10个元素）时运行得很好，但当输入文件有100000个元素时，结果似乎不正确，有时候比实际值大，有时候又比实际值小。有没有人知道这是怎么回事？

我的代码返回的结果是2402298631。输入文件的位置在这里：http://spark-public.s3.amazonaws.com/algo1/programming_prob/IntegerArray.txt

def msort_inv2(m):

    global count

    if len(m) <= 1:
        return m
    result = []
    middle = int(len(m)/2)

    left = msort_inv2(m[:middle])
    right = msort_inv2(m[middle:])

    while (len(left) > 0) or (len(right) > 0):
        if (len(left) > 0) and (len(right) > 0):
            if left[0] > right[0]:
                result.append(right[0])
                count = count + len(left)
                right.pop(0)
            else:
                result.append(left[0])
                left.pop(0)
        elif len(right) > 0:
            for i in right:
                result.append(i)
                right.pop(0)
        else:
            for i in left:
                result.append(i)
                left.pop(0)
    return result

Answer 1

这个问题出现在下面的代码部分

    elif len(right) > 0:
        for i in right:     # bug !!!!
            result.append(i)
            right.pop(0)
    else:
        for i in left:
            result.append(i)
            left.pop(0)

修正的方法应该是这样的

    elif len(right) > 0:
        result.extend(right)
        right = []
    else:
        result.extend(left)
        left = []

在一个数组中使用for循环的同时删除元素，会导致在Python中出现奇怪的行为。