I am trying to count the number of inversions in an array using merge sort.
The idea being that the merge step naturally lends itself to what an inversion is: the ith element being greater than the jth element.
def merge_and_count(x, y, result, count):
i, j = 0, 0
while i < len(x) and j < len(y):
if x[i] > y[j]:
result.append(y[j])
j += 1
count += 1
else:
result.append(x[i])
i += 1
result += x[i:]
result += y[j:]
return result, count
def sort_and_count(array):
if len(array) == 1:
return array, 0
count = 0
result = []
mid = len(array)//2
x = array[:mid]
y = array[mid:]
x, c1 = sort_and_count(x)
y, c2 = sort_and_count(y)
result, c3 = merge_and_count(x, y, result, count)
return result, (c1+c2+c3)
def main():
array = [1,3,5,2,4,6]
result, count = sort_and_count(array)
print("there are", count, "split inversion")
print(result)
However this is printing 2 when I the answer should be 3
There's a bug in your merge_and_count function. It should be:
if x[i] > y[j]:
result.append(y[j])
j += 1
count += len(x) - i # It's not +1 here
When you append the next element from y to the result, it forms an inversion with all elements from x that haven't been added yet. There're exactly len(x) - i such elements.