Recursive merge-sort inversion count algorithm very slow
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] &lt; 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.