Inversion Count In Array Using Merge Sort

 


Inversion count is surely one of the most asked interview topics! 


Most of the time interviewers don’t resist themselves in regard to asking questions related to the inversion count. 


The concept may seem  challenging, but once learned it can become quite interesting. 


Count inversion in any given array indicates how far your array is from being sorted. If your array is already sorted, the inversion count would be 0. Though, if it is sorted in the reverse level order traversal, your inversion count will be maximum. 


The spectrum of this concept is quite wide. One topic that will be commonly asked is; inversion count in a given array using merge sort. 


Well, if you are on this subject and want to have a better detailing of it, we got you covered! 


Here, in this blog, we are going to uncover all the essential information related to inversion count with merge sort. 


Without any ado, let’s get started!



About inversion in array


Number of count inversion in a given array is the changes which are required for an array for being sorted. We will categorise our sorting algorithm by swapping the elements. 


We need to see the number of swaps needed to sort an array with the merge sort. If your array will be already sorted, your inversion count would be o. Though, it would be maximum if the array would be reversely sorted. 


The question on it is asked by some of the reputed product companies in the technical interviews. 



What is a merge sort algorithm?


The merge sort algorithm is defined as a sorting algorithm that divides array collection into the halves and then sorts each one separately. It then merges it into a single and then to the full elements. 

For small subarrays, we will use insertion sort to make our algorithm better. 


Let’s understand inversion count in merge algorithm with the help of a problem statement 


An array of n elements is given to you. You have to count the count of inversions in a given array.  


Count inversions in any given array means how far or close your array is from being sorted. In simpler words, a [i] and a [j] are two elements for a given array. 


If the given array is already sorted, the inversion count would be 0. Though, if the array is reversed sorted, the count would be maximum. 


Let’s look at the example 


Input: a [] = [ 6, 3, 2]


Output would be 3 


Explanation: 


The formed inversions here are; [ 6, 3] , [ 6, 2] and [ 3, 2]


Approach:


In your merge algorithm approach, we will divide the given array into two halves [ starting from left half to the right half] and sort both of the halves using recursion. 


After that we will merge both of the sorted halves to get the final sorted array. Here, in this approach, we will first sort the count number of all inversions in a given array with efficiency. 


Divide the given array into the two halves and suppose count inversions for the left and right halves would be inv_1 or inv_2 respectively. 


The total inversion count in a given array would be the sum of inv_1 and inv_2 respectively and will move to the merging step. 



Count inversions in the merge step 


Let's suppose i is used to index the left half and j will be used to index the right half of any given array in the merging process. So if the a[i] will be greater than the b[j] at any given time, there will be [ half - i ] inversions. 


As the left and right subarrays will be sorted, all the remaining elements will be greater than the b [j] 


Steps in the algorithm:


  • Divide given array into two equal or almost the same halves in each step until the base case will be reached

  • Create a merge inv function which will count all the count of inversions where the left and right halves will be merged. If your a[i] is greater than the b[j] at any given point in the merge(), you will get [ half - i] inversions. As you will get sorted left and right subarrays, remaining elements will be greater than the b[j] 

  • Create a recursive function wherein you will split the array in half and find all the answers by adding number of inversions in your first half, then with the count of inversions in the second half by merging it with the two halves

  • Base case will be the one where there will be only one element in the given subarray

  • Print your result 



Time complexity 


The time complexity in this case will be; O [ N*logN] 


We will use the divide and conquer algorithm at each level. When one traversal of a given array is required and there will be logn levels, you will get this time complexity. 


The space complexity in this case would be O[n] as we are using temporary array [ tmp] 



Brute Force Approach 


Another approach for using merge sort would be to use brute force method. 


Divide an array into two halves until you will get all the single elements [ just like the first step of your classic merge algorithm]. Then we will start merhing it by keeping the definition of count inversion in mind. 


Each time start by merging the two parts of your array. We can also observe here that each time we are making comparisons of our two sorted arrays i.e the left array and the right array. So that the particular position of both the array elements will be in a good stint. You can further count all the elements that are present in the given array. 



Wrapping Up 


Count inversion in a merge sort is a vital topic to be learned by every programmer. We hope that this tutorial will help you get inversion count with the merge sort algorithm. 


Furthermore, you can keep a strong hold on the concept of reverse level order traversal for better understanding of coding. 


Get started today!

Comments

Post a Comment

Popular posts from this blog

What are the 5 types of inheritance?

Image
  The concept of inheritance is considered among the most crucial concepts of object-oriented programming. Inheritance in Java is considered as a process where one class inherits the property of its parent class. When we simply define inheritance, we call it the capability of a class that derives the properties or features of other classes. The new class will be created as the ‘ derived class’ and the existing class will be known as base or parent class. Talking about the types of inheritance, it is generally of five types. Here, in this blog we are going to discuss all these inheritance types in detail with the help of examples. Without any ado, let’s get started! Types of inheritance In case of inheritance, one class derives the properties from its parent class. Here, any new class will be derived from its existing class. This new class is the derived class and our current class will be termed as the base class. When we talk about inheritance in Java, there are mainly five types ...
Read more

Remove duplicates from a sorted linked list

Image
Introduction Before reading this article, It is recommended to have an understanding of the linked list and its implementation and some basic operations on the linked list. Problem Description Create a function that takes a non-descending list and removes any duplicate nodes. Only one traversal of the list is necessary. Eg. Consider the given linked list: 1->1->1->2->2->3, the function is expected to convert the linked list into 1->2->3. In this article, we will extensively discuss the Label Control in C# & how to  remove duplicates from sorted doubly linked list .  Important:  We are supposed to delete only the duplicates i.e. only one copy of nodes should be there. Intuition:  The biggest hint given is that the list is sorted or non-decreasing in nature. From this, we can deduce that if duplicates are present, then it has to be the next one in the chain. The ideal way to approach this problem is to simply loop through the first value i...
Read more

How often can you Buy and Sell the same stock?

Image
The stock market is notoriously unpredictable. It can be hard enough to guess whether or not a particular investment will pay off or not. We know that understanding all the nuances of rules and regulations involved when buying and selling stocks is difficult. One big question many people have is, “How often can you buy and sell the same stock with transaction fee ?”  Before you start trading, you are unaware of the steps to follow to start trading and what would be the best time to buy and sell stock with transaction fee.  No matter if this is your first time investing or if you’ve been around the block a few times before, we hope that our guide will help you understand briefly on how to sell and buy stocks with in same time. Let's start with understanding stock trading and the types of traders in detail. What is Stock trading? The term "stock trading" describes the purchasing and selling of equities on a stock market. Investors that purchase and sell stocks with the inte...
Read more