This C++ Program demonstrates the implementation of Inversion Count of an Array.

Here is source code of the C++ Program to Count Inversion in an Array. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C++ Program to Count Inversion in an Array`

`*/`

`#include <iostream>`

`#include <cstdlib>`

using namespace std;

int mSort(int arr[], int temp[], int left, int right);

int merge(int arr[], int temp[], int left, int mid, int right);

`/*`

`* calls mSort`

`*/`

int mergeSort(int arr[], int array_size)

`{`

int *temp = new int [array_size];

return mSort(arr, temp, 0, array_size - 1);

`}`

`/*`

`* sorts the input array and returns the number of inversions in the array.`

`*/`

int mSort(int arr[], int temp[], int left, int right)

`{`

int mid, inv_count = 0;

if (right > left)

`{`

mid = (right + left)/2;

inv_count = mSort(arr, temp, left, mid);

inv_count += mSort(arr, temp, mid+1, right);

inv_count += merge(arr, temp, left, mid+1, right);

`}`

return inv_count;

`}`

`/*`

`* merges two sorted arrays and returns inversion count in the arrays.`

`*/`

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))

`{`

if (arr[i] <= arr[j])

`{`

temp[k++] = arr[i++];

`}`

`else`

`{`

temp[k++] = arr[j++];

inv_count = inv_count + (mid - i);

`}`

`}`

while (i <= mid - 1)

temp[k++] = arr[i++];

while (j <= right)

temp[k++] = arr[j++];

for (i = left; i <= right; i++)

arr[i] = temp[i];

return inv_count;

`}`

`/*`

`* Main`

`*/`

int main()

`{`

int arr[] = {1, 20, 6, 4, 5};

cout<<"Number of inversions are "<<mergeSort(arr, 5)<<endl;

return 0;

`}`

$ g++ inversion_count.cpp $ a.out Number of inversions are 5 ------------------ (program exited with code: 1) Press return to continue

**Sanfoundry Global Education & Learning Series – 1000 C++ Programs.**

If you wish to look at all C++ Programming examples, go to C++ Programs.