c++ count inversions merge sort

Merge sort is a popular sorting algorithm that can be used to sort an array in ascending order. It is based on the divide and conquer strategy, where the array is divided into two halves, sorted individually, and then merged back together to obtain the final sorted array.

To count inversions using merge sort, we can modify the merge step of the algorithm to keep track of inversions. An inversion occurs when two elements in the array are out of order, i.e., the element on the left is greater than the element on the right.

Here is a step-by-step explanation of how to count inversions using merge sort in C++:

  1. Merge Function: First, we need to implement a merge function that will merge two sorted arrays into a single sorted array. The merge function takes two arrays, left and right, along with their sizes, n1 and n2, respectively. It also takes an output array, arr, to store the merged result. The function compares elements from left and right arrays and copies them to arr in a sorted order.

  2. Merge Sort Function: Next, we implement the merge sort function that will sort the given array and count inversions. The merge sort function takes an array, arr, along with its starting and ending indices, l and r.

  3. Base Case: The merge sort function has a base case when l becomes greater than or equal to r, indicating that there is only one element in the array. In this case, the function simply returns.

  4. Divide: The merge sort function calculates the middle index, m, as the average of l and r. It then recursively calls the merge sort function on the left half of the array, from l to m, and the right half of the array, from m+1 to r.

  5. Conquer: Once the left and right halves are sorted, the merge function is called to merge the two sorted halves into a single sorted array. During the merge, the merge function also counts the number of inversions.

  6. Counting Inversions: To count inversions, we introduce a variable, count, to keep track of the number of inversions. During the merge step, when an element from the right array is chosen and copied to the output array arr, we increment count by the number of remaining elements in the left array.

  7. Return: Finally, the merge sort function returns the total number of inversions.

By using this modified version of the merge sort algorithm, you can efficiently count inversions in an array.