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 > array: 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)
source to share