👀 Views: 200 💬 Answers: 1 📅 Created: 2025-06-13

merge-sort algorithms python inversions Python

I'm performance testing and I'm implementing a modified merge sort algorithm in Python to count the number of inversions in an array... However, I'm working with incorrect results in edge cases, particularly when the input array is already sorted or contains duplicate elements. My implementation is based on the standard merge sort algorithm but includes a count mechanism to track inversions. Here’s the relevant part of my code: ```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 merged 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 ``` When I run this code with an already sorted array like `[1, 2, 3, 4, 5]`, I expect the output to be `0`, but it’s returning `2`. I've also tested it with arrays containing duplicates, such as `[1, 1, 1, 1]`, and I get `4` instead of `0`. I've confirmed that the merge logic is implemented correctly, and I'm not sure where I'm going wrong. Here’s how I’m calling the function: ```python arr = [1, 2, 3, 4, 5] temp_arr = [0] * len(arr) result = merge_sort_and_count(arr, temp_arr, 0, len(arr) - 1) print(f'Number of inversions: {result}') ``` Could someone guide to figure out what I’m missing in this implementation? Any insights into debugging this scenario would be greatly appreciated! I'm on Linux using the latest version of Python. Hoping someone can shed some light on this.