Алгоритм Число инверсий (Python)

Question

Я пытаюсь выполнить назначение кода для Algorithmic Toolbox, предлагаемого UC San Diego на Coursera. Присвоение требует, чтобы вы посчитали количество инверсий в последовательности чисел, используя вариацию алгоритма сортировки слиянием. Для лучшего описания проблемы:

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

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

В основном за пределами обычной отладки я пытался сравнить мой код с известными решениями, чтобы понять, где я могу ошибаться. Я мог бы представить их в качестве своего решения, но, насколько я понимаю, это будет чит, и я хотел бы знать, где я ошибся с моим кодом (и это, честно говоря, сводит меня с ума).

#Uses python3
import sys

def merge_sort(A):
    if len(A) <= 1:
        return A, 0    
    else:
        middle = (len(A)//2)
        left, count_left = merge_sort(A[:middle])
        right, count_right = merge_sort(A[middle:])
        result, count_result = merge(left,right)
        return result, (count_left + count_right + count_result)

def merge(a,b):
    result = []
    count = 0
    while len(a) > 0 and len(b) > 0:
        if a[0] < b[0]:
            result.append(a[0])
            a.remove(a[0])
        else:
            #count = count + (len(a) - 1)
            result.append(b[0])
            b.remove(b[0])
            count += (len(a) - 1) #this is the important line
    if len(a) == 0:
        result = result + b
    else:
        result = result + a
    return result, count 

if __name__ == '__main__':
    input = sys.stdin.read()
    n, *a = list(map(int, input.split()))
    c = n * [0]
    array, inversion = merge_sort(a)
    print(array)
    print(inversion)

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

# ex 1:
3
3 1 2

Обратите внимание, что первая цифра - это число значений в последовательности (требуется для грейдера). Ожидаемый ответ для инверсий - 2. Я получаю 0 с моим кодом.

# ex 2:
6
3 1 9 3 2 1

Ожидаемый ответ для инверсий - 9. Я получаю 4.

Answer 1

Два исправления:

if a[0] <= b[0]: (обратите внимание, что многие примеры и курсы в Интернете игнорируют or equal случай, разрушающий внутреннюю устойчивость алгоритма, этот случай также важен для правильной инв. считая)

а также count += len(a) - мы должны учитывать, что все предметы в a формировать инверсии с током b вещь

def merge(a,b):
    result = []
    count = 0
    while len(a) > 0 and len(b) > 0:
        if a[0] <= b[0]:   
            result.append(a[0])
            a.remove(a[0])
        else:
            result.append(b[0])
            b.remove(b[0])
            count += len(a)
    if len(a) == 0:
        result = result + b
    else:
        result = result + a
    return result, count