количество инверсий с использованием сортировки слиянием python

Я реализую сортировку слиянием с инверсией. мой код отлично работает с моим небольшим входным файлом (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

person RRock    schedule 08.08.2014    source источник
comment
Пожалуйста, предоставьте минимальный пример вашего кода и лучшее описание проблемы, чем кажется неправильным (предоставьте входные данные и ожидаемые и фактические результаты).   -  person jonrsharpe    schedule 08.08.2014
comment
может помочь, если вы разместили код   -  person Padraic Cunningham    schedule 08.08.2014
comment
Вы имеете в виду, что ваш код «возвращает» или «выводит» 2402298631?   -  person miindlek    schedule 08.08.2014


Ответы (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.

person RRock    schedule 20.08.2014