When will the following inversion counting algorithm using merge sort fail
I wrote the following code to count the number of inversions in an array of numbers. It gives correct results for the input I tested, but still it failed the test cases, I don't have access to the test cases I can't figure out in what cases it will fail, I can really use some help here.
def count_inversion(array):
"""
counts number of inversions in array using divide and conquer
an inversion is a pair (x,y) such that x > y, example in array
[3,1,2] there are two inversions (3,1), (3,2)
"""
length = len(array)
if length == 1 or length == 0:
return array,0
elif length == 2:
if array[0] > array[1]:
array.sort()
return array,1
else:
return array,0
else:
left_array,left_count = count_inversion(array[:length/2])
right_array,right_count = count_inversion(array[length/2:])
across_arr,across_count = count_split(left_array,right_array)
return across_arr,left_count + right_count + across_count
def count_split(left,right):
"""
counts the number of inversions across split pair
left and right, by piggy backing on merge routine
of merge sort
"""
l = 0
r = 0
merge = []
count = 0
inversions = 0
last_r = 0
try:
while True:
if left[l] > right[r]:
merge.append(right[r])
if r == 0 or r == last_r:
inversions = 0
inversions += 1
r = r + 1
else:
merge.append(left[l])
count = count + inversions
l = l + 1
last_r = r
except IndexError:
if r == len(right):
while l < len(left):
count += inversions
merge.append(left[l])
l = l + 1
else:
while r < len(right):
merge.append(right[r])
r = r + 1
return merge,count
if __name__ == '__main__':
f = open('inversions.txt')
arr = []
for line in f:
arr.append(int(line))
# arr is a list of integers which are not sorted in any sense
# we are required to count number of inversions in arr
print count_inversion(arr)[1]
+3
source to share