Algorithm Number of Inversions (Python)

Question

I'm attempting to complete a code assignment for the Algorithmic Toolbox offered by UC San Diego on Coursera. The assignment requires that you count the number of inversions in a sequence of numbers using a variation of the merge-sort algorithm. For a better description of the problem:

https://i.sstatic.net/CCBU8.jpg

I've used a variation of a merge-sort algorithm but am getting an incorrect answer and am frankly stuck.

Of note is that before explaining what I've attempted is that this code involves recursion which I admit I'm finding tricky to understand.

Mostly beyond the usual debugging I've tried to compare my code to known solutions to see where I may be going wrong. I could submit those as my solution but as far as I'm concerned that would be a cheat and I'd like to know where I've gone wrong with my code (and it's quite honestly driving me nuts).

#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)

Listed below are two sample inputs I have been using in my testing:

# ex 1:
3
3 1 2

Note that the first digit is the number of values in the sequence (required for the grader). Expected answer for inversions is 2. I'm getting 0 with my code.

# ex 2:
6
3 1 9 3 2 1

Expected answer for inversions is 9. I'm getting 4.

Answer 1

Two corrections:

if a[0] <= b[0]: (note that a lot of internet examples and courses ignore or equal case, destroying intrinsic algorithm stability, this case also is important for correct inv. counting)

and count += len(a) - we need to account that all items in a form inversions with current b item

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