Count Inversions in an array Set 1 Using Merge Sort GeeksforGeeks

Hello everyone! And, welcome to GeeksforGeeks. In this tutorial we are going to see how to count the number of inversions in an array. First of all let us try to understand what do we mean by an inversion. So an element at index I and element at index j form an inversion if the value of element at index i is greater than value of element at index j whereas value of I is smaller than value of j. For example, in the given sequence 2,4,1,3,5 there are a total of 3 inversions. Let us look at them one by one So first of all we look at elements 2 and 1 highlighted in red. Here 2 > 1 whereas index of 2 < index of 1. So they form an inversion. Similarly the element 4 and 1 form an inversion as 4 > 1 whereas index of 4 is smaller than index of 1. Finally we look at element 4 and 3. They also form an inversion as 4 > 3 but index of 4 is smaller than index of 3. In this problem we basically have to find out the inversion count of the array. Inversion count actually tells how far or how close the array is from being sorted. So if the array is completely sorted, there will not be any inversions in the array and thus the inversion count will be zero. However, if the array is sorted in reverse order, the inversion count will be the maximum possible inversion count value for any array of that size. First of all, letís look at the simplest method. In this method we iterate over the array element by element and for each element we check the number of smaller elements to the right of the selected element. So you see the method getInvCount, we first of all initialize inv_count as zero. Then we run a loop from 0 to n-1 where n is the total number of elements. Then for each element, we run a loop from the element to itís right to element at index n-1. Whenever we encounter any element which is smaller than given element, we increment the inv_count. Finally we return the inv_count. This method solves the problem in Order of n squared time complexity. Now weíll look at the solution in which we will be using enhanced merge sort to count the number of inversions in an array. But firstly weíll quickly recapitulate the original merge sort algorithm. Merge sort works on divide and conquer paradigm i.e. we keep recursively dividing the given problem into smaller sub problems until they become simple enough to be solved directly, then solutions of the subproblems are combined to give solution to the original problem. Given an array, we first of all divide the array into two halves. Then we call the mergeSort on each of those halves and then we finally merge those two sorted subarrays. Here is the big picture of enhanced merge sort algorithm. We divide the array recursively into two halves and compute the answer for those two sub-halves. Now suppose we know the number of inversions in the left and right halves of the array, then what kinds of inversions are not accounted for in inv1 + inv2 ? Well the answer is the ones we have to count during the merge step. Therefore to get the total number of inversions we need to add number of inversions in the left subarray, right subarray and in the merge step. Now the question is how do we get the number of inversions in the merge operation? To answer that let I be used for indexing left subarray and j be used for indexing right subarray. At any step in merge if value of element at index i is greater than value of element at index j, then we know that there are (mid-i) inversions. This is because both left and right subarrays are already sorted, so if element at index i is greater than element at index j, then all the elements in the left subarray with index greater than i will also be greater than element at index j. Let us try to understand this with the help of an example. So here you have the left and right half of the array. Notice that both of these are already sorted individually. So we start with index i=0 and index j =3 whereas the mid index is 3 because from index 3 the right subarray starts. Also the initial inversion count is set as Zero. Now we compare the two highlighted elements. 1 is smaller than 2, So we move it in the merged array and the inversion count remains zero. Now we compare 3 with 2. As 3 is greater than 2, weíll move the smaller element i.e. 2 in the merged array. But before that we see that we have encountered an inversion. Although value of 3 is greater than value of 2, but the index of element 2 is smaller than index of 3. We already know that first subarray is sorted. So elements coming after 3 will be greater than 3 and thus will also be greater than value 2. So they all form pairs of inversions with element 2. So in total we see that there are mid index-i i.e. 3-1=2 inversions in this step. So weíll increment the value of inversion count by 2. Now we compare 3 with 4. As 3 is smaller than 4, we move the value 3 to sorted array and increment the value of i. Now we compare 5 with 4. Clearly 5 is greater than 4 but index of 5 is smaller than index of 4. So we have again found an inversion. As per our algorithm, weíll add mid index ñ i i.e. 3-2=1 inversions in the inversion count. After that weíll move 4 into the sorted array and increment the value of index j. Now we compare 5 with 6. As 5 is smaller than 6, we move the value 5 to sorted array. Now as all the elements of left subarray are already processed, weíll just move the remaining elements of right subarray to the sorted array. After all elements are processed and moved to sorted merged array, we have the inversion count of the merge step as 3. Now letís understand the algorithm better with the help itís implementation. So the implementation starts with the mergeSort function which takes as an argument the array and itís size. Inside this function, we create a temporary array and pass it to _mergesort method along with the original array. We also pass the starting and ending index of array i.e. 0 and array_size -1 respectively. Now lets see the _mergeSort method. Here we declare the variables mid and inv_count. We also initialize the inversion count with value zero. Here we check if right is greater than left, then we do the following. We calculate the value of mid as right + left/2. Now as per the algorithm, we call the _mergeSort method for left subarray and right subarray. Notice that left subarray is from left to mid index whereas the right subarray is from mid+1 to right. We add the inversion counts returned by these respective calls to inv_count variable. Finally we call the merge method to merge the left and right subarrays and add the inversion count returned by _merge method to inv_count variable. Lastly, we return the value of inv_count. In merge method, we first of all declare variables i, j and k. Then we declare inv_count and initialize it as zero. Then we initialize variable i as left, j as mid and k as left. Then while either one of the array is not completely processed, we do the following. We compare the element at index i with element at index j. If element at index i is smaller than or equal to element at index j, then we just copy the element at index i to temp array and increment the values of k and i. Otherwise we copy the value at index j to temp array and increment the value of both k and j. Additionally, as per the algorithm which we discussed, we encounter the inversions in this case, so we add mid-i inversions to inv_count. Once this is done, we copy the remaining elements of left subarray, if any, to temp array. Then similarly we copy the remaining element of the right subarray, if any, to temp array. Finally, copy the values from temp array back to our original array and return the inv_count value. Now coming to the time complexity. The time complexity of this solution is same as of the merge sort algorithm i.e. O(nlogn) and the algorithmic paradigm used is Divide and conquer. So in total we discussed two methods to solve the problem. The first one was simple method which solved the problem in Order of n squared time complexity whereas the 2nd method using the enhanced merge sort solved the problem in Order of n log n time complexity. So that is all for this tutorial. Thank you.

Loading