Counting Inversion
An inversion in an array refers to a pair of elements (a[i], a[j]) where i < j but a[i] > a[j]. The count of inversions measures how far the array is from sorted order.
Java example using merge sort:


C++ example using BST:


Python example using brute force:


Inversion count is useful for quantifying presortedness and analyzing sorting algorithms.
In computer science and algorithms, counting inversions is a fundamental concept often used in sorting and ranking problems. An inversion is a pair of indices ( (i, j) ) such that ( i < j ) but ( A[i] > A[j] ). Counting inversions in an array helps to quantify how far the array is from being sorted. A sorted array has zero inversions.
Example Code
Java


C++


Python


All the example codes above have a time complexity of ( O(n^2) ).
Q&A
What is the largestpossible number of inversions a 6element array can have?
The largestpossible number of inversions a 6element array can have is when the array is sorted in descending order. In this case, every pair of elements ( (i, j) ) where ( i < j ) will be an inversion.
For a 6element array, you can calculate the largestpossible number of inversions by considering each element and how many elements are greater than it and come before it in the array.
Mathematically, for an array of ( n ) elements, the largestpossible number of inversions is ( \frac{n * (n  1)}{2} ).
So, for a 6element array:
[ \text{Largestpossible number of inversions} = \frac{6 * 5}{2} = 15 ]
Can we do better than the quadratic time complexity for this problem?
Yes, the problem of counting inversions can be solved more efficiently than in quadratic time. One common approach is to use a modified Merge Sort algorithm. This algorithm works in ( O(n \log n) ) time, which is more efficient than the ( O(n^2) ) time needed for a naive approach that checks every pair.
In the modified Merge Sort, while merging two sorted halves, we count the number of inversions where the first element is in the left half and the second element is in the right half. These are precisely the inversions that a regular Merge Sort would “fix” during the merge step.
By counting these inversions at each recursive merge step and summing them up, we can count all inversions in the array. This maintains the ( O(n \log n) ) time complexity of the Merge Sort algorithm.