Recursive merge-sort inversion count algorithm very slow

Question

I am trying to implement a recursive count of inversions in a list of integers by using merge sort and counting the number of split inversions on each recursion. My code works but runs painfully slowly above a list of about 100 integers, and I need to count for ~3 orders of magnitude greater. Can anyone see what I'm doing wrong that makes it so slow?

inversions = np.loadtxt("inversion_text.txt", int).tolist()

def sort_count_inversions(X):
    n = len(X)

    # For subproblems of size 1 there are no inversions and no sorting required
    if n == 1:
        return 0, X
    a = X[:n//2]
    b = X[n//2:]

    # Count the inversions in subproblems
    # Get back the count of inversions and the sorted subproblems
    count_a, sorted_a = sort_count_inversions(a)
    count_b, sorted_b = sort_count_inversions(b)

    # Count the split inversions between sorted sub problems
    # Get back the count of split inversions and the the merge-sorted subproblems (sorted X)
    split_count, a_b = merge_count_split_inversions(sorted_a,sorted_b)

    # return the count of inversions in X and merge-sorted X
    count = split_count + count_a + count_b
    return count, a_b


def merge_count_split_inversions(X, Y):
    n = len(X) + len(Y)
    j = 0
    k = 0
    X_Y = []
    count_split = 0

    # Iterate through X and Y comparing value by value
    for i in range(n):
        # If we have reached the end of X or Y, there are no more inversions so append the remaining values to X_Y
        if j == len(X):
            X_Y.extend(Y[k:])
        elif k == len(Y):
            X_Y.extend(X[j:])
        # Add the smaller of the two compared elements to X_Y
        # If adding from Y, increment count of split inversions by the number of remaining elements in X
        elif X[j] < Y[k]: 
            X_Y.append(X[j])
            j += 1
        else:
            X_Y.append(Y[k])
            k += 1
            count_split += len(X) - j

    # Return the total count of split inversions and the result of merge_sorting X and Y (X_Y) 
    return count_split, X_Y 

sort_count_inversions(inversions)

Answer 1

There's a bug in merge_count_split_inversions.

    for i in range(n):
        if j == len(X):
            add len(Y)-k elements to X_Y
        elif k == len(Y):
            add len(X)-j elements to X_Y
        elif X[j] < Y[k]:
            add 1 element to X_Y
            j += 1
        else:
            add 1 element to X_Y
            k += 1

This should have the invariant that after the ith time round the loop it has added i elements to X_Y. Either the first two cases need to add a single element, or they need to break.