implementing Implementing a Merge Sort Algorithm in Python - Unexpected Inversions Count
I'm working on a project and hit a roadblock... I'm currently working on implementing a Merge Sort algorithm in Python, which I need not only to sort an array but also to count the number of inversions present in it. I've based my implementation on the typical recursive merge sort but something seems to be off. The output is correct for sorted arrays but fails on unsorted input. Here’s the code I’ve written: ```python def merge_and_count(arr, temp_arr, left, mid, right): i = left # Starting index for left subarray j = mid + 1 # Starting index for right subarray k = left # Starting index to be sorted inv_count = 0 while i <= mid and j <= right: if arr[i] <= arr[j]: temp_arr[k] = arr[i] i += 1 else: temp_arr[k] = arr[j] inv_count += (mid - i + 1) j += 1 k += 1 while i <= mid: temp_arr[k] = arr[i] i += 1 k += 1 while j <= right: temp_arr[k] = arr[j] j += 1 k += 1 for i in range(left, right + 1): arr[i] = temp_arr[i] return inv_count def merge_sort_and_count(arr, temp_arr, left, right): inv_count = 0 if left < right: mid = (left + right) // 2 inv_count += merge_sort_and_count(arr, temp_arr, left, mid) inv_count += merge_sort_and_count(arr, temp_arr, mid + 1, right) inv_count += merge_and_count(arr, temp_arr, left, mid, right) return inv_count # Test the function arr = [2, 3, 8, 6, 1] temp_arr = [0] * len(arr) result = merge_sort_and_count(arr, temp_arr, 0, len(arr) - 1) print(f'Number of inversions are: {result}') ``` When I run this with the input array `[2, 3, 8, 6, 1]`, I expect an output of `5` since the pairs (2, 1), (3, 1), (8, 6), (8, 1), and (6, 1) are the inversions. However, the output I am getting is `7`, which doesn't make sense. I've double-checked the logic for counting inversions in the `merge_and_count` function, but I need to seem to pinpoint where it might be going wrong. It seems like the counting is somehow including extra pairs. I’m using Python 3.9.1. Any help in debugging this scenario would be greatly appreciated! I'm working on a API that needs to handle this.