**What is an inversion?**

Let A be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.

For example, the array {2,3,8,6,1} has 5 inversions: (2,1) (3,1) (8,6) (8,1) and (6,1)

**Trivial Solution to count the number of inversions in an array**

countInversions = 0; for i = 1 to N for j = i+1 to N if(A[i] > A[j]) countInversions++;

The overall time complexity for this approach is O(n^**2**)

**Using Merge Sort to count the number of inversions in O(n logn) time**

Merge-Sort is a divide-and-conquer strategy where the array is divided into two halves, each half is sorted and the the sorted halves are merged back together in sorted order.

MERGE-SORT(A, start, end) { if(start < end) { mid = (start + end) / 2; MERGE-SORT(A, start, mid); MERGE-SORT(A, mid + 1, end); MERGE(A, start, mid, end); } }

The Merge Operation in Merge Sort is described below. The values in the two halves are copied to two temporary arrays. The elements from these arrays are then added back into the main array in sorted order.

MERGE(A, start, mid, end) { firstArray = new Array of size mid – start + 2; secondArray = new Array of size end – mid + 1; Copy values from A[start: mid] to firstArray[0: mid-start]; Copy values from A[mid+1: end] to secondArray[0: end-mid-1]; firstArray[mid-start+1] =∞secondArray[end-mid] =∞i = 0, j = 0; for k = start to end { if(firstArray[i] <= secondArray[j]) { A[k] = firstArray[i]; i++; } else { A[k] = secondArray[j]; j++; } } }

Can you think of how you would modify MERGE-SORT to count the number of inversions? Take your time and think about your solution before reading further.

**Modified Merge-Sort**

intMERGE-SORT(A, start, end) {int countInversions = 0;if(start < end) { mid = (start + end) / 2;countInversions +=MERGE-SORT(A, start, mid);countInversions +=MERGE-SORT(A, mid + 1, end);countInversions +=MERGE(A, start, mid, end); }return countInversions;}intMERGE(A, start, mid, end) { firstArray = new Array of size mid – start + 2; secondArray = new Array of size end – mid + 1; Copy values from A[start: mid] to firstArray[0: mid-start]; Copy values from A[mid+1: end] to secondArray[0: end-mid-1]; firstArray[mid-start+1] =∞secondArray[end-mid] =∞i = 0, j = 0,countInversions = 0;for k = start to end { if(firstArray[i] <= secondArray[j]) { A[k] = firstArray[i]; i++; } else { A[k] = secondArray[j]; j++;countInversions += firstArray.length – i - 1;} }return countInversions;}

Do you think this will work? Please simulate this once yourself and see!

This content was brought to you by CodeGround Online Testing Platform. CodeGround is an online assessment and test evaluation system focused on helping Recruiters in initial screening of potential candidates from an ocean of job seekers in an automated way.

CodeGround supports Online Aptitude Tests, Spoken English Communication Skills Assessments, Coding Contests in JAVA, C, C++, Ruby, Python, JavaScript and PHP. CodeGround also supports Automated asynchronous interviews. CodeGround Screening Tests can be used by Recruiters during campus hiring or to screen walkin candidates.