def mergeCount(left,right,invCount): inversionCount = invCount # print(left,right) for right_item in right: offset = 0 insertState = False for i in range(len(left)): if left[i] <= right_item: offset += 1 elif left[i] > right_item: inversionCount += len(left) - offset left.insert(i,right_item) # print("inserted",right_item) insertState = True break if not insertState: left.append(right_item) # print("new array is",left) return left,inversionCount def mergeSortInversion(array): if len(array) <= 1: return array,0 else: left_arr, left_count = mergeSortInversion(array[:len(array)//2]) right_arr, right_count = mergeSortInversion(array[len(array)//2:]) # print(left_arr,right_arr,left_count+right_count) return mergeCount(left_arr,right_arr,left_count + right_count)
My merge sort code is taking the same amount of time as the brute force method for some reason. How can I fix the implementation / make it better?