Странное поведение в списке с 100000 элементами

Question

Я присоединился к онлайн-курсу Standford по разработке алгоритмов, и теперь я решаю первый вопрос программирования.

The file содержит все целые числа от 100000 до 100000 1 (в том числе и) в некоторой случайном порядке (не целое число, не повторяется). Задача состоит в том, чтобы найти количество инверсий в указанном файле (каждая строка имеет одно целое число от 1 до 100 000). Предположим, что ваш массив от от 1 до 100 000, а i-я строка файла дает i-ю запись массива .

Обновление: Я обнаружил, что мой код работает только для случая 2^n. Проблема заключается в коде, а не в Python. Я обновил код, теперь он отлично работает, и я сделал викторину. Спасибо всем, кто помог

Фиксированный код:

def merge_count_split (a, b): 
     c = [] 
     inv = 0 
     i=0 
     j=0 
     for k in range(len(a) + len(b)): 
       if i < len(a) and j < len(b): 
         if a[i] < b[j]: 
           c.append(a[i]) 
           i += 1 
         elif a[i] > b[j]: 
           c.append(b[j]) 
           inv += len(a)-i 
           j += 1 
       elif i == len(a): 
         c.append(b[j]) 
         j += 1 
       elif j == len(b): 
         c.append(a[i]) 
         i += 1 
     return c, inv 

def count_inv (data): 
     n = len(data) 
     if n == 1: 
       return data, 0 
     a, x = count_inv(data[:n/2]) 
     b, y = count_inv(data[n/2:]) 
     c, z = merge_count_split(a,b) 
     return c, x + y + z 

with open('IntegerArray.txt') as f: 
     array = [int(line) for line in f] 
     print count_inv(array)[0] 

Эта программа прекрасно работает для небольших массивов, но для большого массива из вопроса печатает массив чисел в правильном порядке, не 100000, как я ожидаю. Он пропускает числа в случайных местах.

В чем причина этого неожиданного поведения python?

Answer 1

Установив n = len(a) и слияние только n * 2 раз, вы обрезаете b, если оно больше a.

Это частично объясняет поразительный факт, что у вас есть 2 ** 16 предметов в результирующем списке.