Merge Sort не работает с большим набором данных

Question

Я пытаюсь использовать алгоритм сортировки слиянием для подсчета инверсий в массиве, который содержит все числа в диапазоне от 1 до 100 000. Он отлично работает при вводе небольшого набора данных, но не возвращает правильный ответ, когда я ввожу файл, содержащий больший массив. Может быть, проблема с тем, как я могу ввести файл? Мне никогда не приходилось вводить файл в массив раньше, поэтому я не могу сказать окончательно, правильно ли я делаю это.

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) 

Это должно возвращать 2407905288, но вместо этого возвращает 2397819672.

Answer 1

Кажется, что это не должно работать в большинстве случаев с цифрами больше 9! Вы сохраняете числа в списке строк. Таким образом, ваш компаратор в функциях слияния сравнивает две строки, так что, например, 2 больше 12!

По крайней мере, вы должны изменить свои первые строки:

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

Answer 2

попробуйте k способ слияние сортировка http://www.sanfoundry.com/java-program-k-way-merge-algorithm/. проблема с большим набором данных заключается в том, что простая сортировка слияния должна приводить к двум большим массивам в основную память во время выполнения, что иногда невозможно.