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
int MERGE-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; } int 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, 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 Evalground Online Testing Platform. Evalground 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.
Evalground supports Online Aptitude Tests, Spoken English Communication Skills Assessments, Coding Contests in JAVA, C, C++, Ruby, Python, JavaScript and PHP. Evalground also supports Automated asynchronous interviews. Evalground Screening Tests can be used by Recruiters during campus hiring or to screen walkin candidates.