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)

• scnerd: Happy to take a look, but have you profiled your code yet?
• scnerd: Could you provide a sample of inversions?
• scnerd: You say the algorithm works, but the sorted result that gets returned is much larger than the original input array. Whatever is causing that might also be the source of the slowness.

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.

• Felix: Great thanks for the spot, all runs fine and quickly now :-)
• 200_success: @Felix I have rolled back Rev 4 → 2. Please see What to do when someone answers .