Related Tags

array
inversions

# How to count the number of inversions in an array Educative Answers Team

The number of inversions in an array indicates the number of changes required in the array for it to be sorted.

## Method

Given an array, if i < j and arr [i] > arr [j] then the pair (i,j) requires an inversion. All such pairs are calculated.

For each element, the naive approach would be to calculate the number of elements to its right that are less than it. The time complexity for this approach would be $O( n^2 )$. However, t​he best approach would be to extend the merge sort. The illustration below shows the method used to calculate the inversions in an array using merge sort:

1 of 16

### Implementation

In the code below, the tmergeSort() function is used to calculate the inversions in the array, recursively. The merge() function is used to merge the two sorted arrays.

Understanding the merge sort is highly recommended.

// Java implementation

class main {

// Function to count Inversions
static int mergeSort(int arr[], int array_size)
{
int temp[] = new int[array_size];
return tmergeSort(arr, temp, 0, array_size - 1);
}

// This function uses merge sort to count inversion.
static int tmergeSort(int arr[], int temp[], int left, int right)
{
int mid, inv_count = 0;
if (right > left) {
// calculating the middle element
mid = (right + left) / 2;

// calculating inversion count for left array
inv_count = tmergeSort(arr, temp, left, mid);
//calculating inversion count for right array
inv_count += tmergeSort(arr, temp, mid + 1, right);

// merging the two arrays
inv_count += merge(arr, temp, left, mid + 1, right);
}
return inv_count;
}

// This function merges the two sorted arrays.
static int merge(int arr[], int temp[], int left, int mid, int right)
{
int i, j, k;
int inv_count = 0;

i = left;
j = mid;
k = left;
while ((i <= mid - 1) && (j <= right)) {
// No inversion will occur
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
// Inversion will occur
temp[k++] = arr[j++];
inv_count = inv_count + (mid - i);
}
}

// the remaining elements of left array are copied.
while (i <= mid - 1)
temp[k++] = arr[i++];

// the remaining elements of right array are calculated.
while (j <= right)
temp[k++] = arr[j++];

for (i = left; i <= right; i++)
arr[i] = temp[i];

return inv_count;
}

// Driver Function
public static void main(String[] args)
{
int arr[] = new int[] { 83, 20, 9, 50, 115, 61, 17 };
System.out.println("Inversions_count = " + mergeSort(arr, 7));
}
}


RELATED TAGS

array
inversions 