合并排序不适用于大数据集

Question

我正在尝试使用合并排序算法来计算包含 1 到 100,000 范围内所有数字的数组中的倒置。当我输入一个小数据集时它工作正常但当我输入包含较大数组的文件时 return 没有正确答案。我输入文件的方式有问题吗？我以前从未需要将文件输入到数组中，所以我不能明确地说我是否正确地做这件事。

file = open('IntegerArray.txt','r')
integerArray = []
for line in file:
    integerArray.append(line)


inversions = 0

def divide(list):
    if len(list) > 1:
        middle = int(len(list) / 2)
        left = divide(list[:middle])
        right = divide(list[middle:])

        #left = divide(left)
        #right = divide(right)

    elif len(list) <= 1:
        return list

    return merge(left,right)

def merge(left,right):
    global inversions
    result = []

    while left != [] and right != []:
        if left[0] < right[0]:
            result.append(left[0])
            if len(left) > 1:
                left = left[1:]
            else:
                left = []
        elif left[0] > right[0]:
            result.append(right[0])
            inversions += len(left)
            if len(right) > 1:
                right = right[1:]
            else:
                right = []

    if left != []:
        result += left
    if right != []:
        result += right

    return result

divide(integerArray)
print(inversions)

这应该 return 2407905288 但 return 应该是 2397819672。

Answer 1

尝试 k 种归并排序 http://www.sanfoundry.com/java-program-k-way-merge-algorithm/。大数据集的问题是简单的合并排序必须在运行时间将两个大数组放入主内存，这有时是不可能的。

Answer 2

似乎它对大多数大于 9 的情况不起作用！您将数字保存在字符串列表中。所以合并函数中的比较器比较两个字符串，例如 2 大于 12！

至少您需要将第一行更改为：

file = open('IntegerArray.txt','r')
integerArray = []
for line in file.readlines():
    integerArray.append(int(line.strip()))

合并排序不适用于大数据集

Merge Sort does not work on large data set

python

algorithm

mergesort