WAp to Count Inversion Count In an Array Linear Time

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example:
The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

METHOD 1 (Simple)
For each element, count number of elements which are on right side of it and are smaller than it.
?
int getInvCount(int arr[], int n)
{
int inv_count = 0;
int i, j;

for(i = 0; i < n - 1; i++)
for(j = i+1; j < n; j++)
if(arr[i] > arr[j])
inv_count++;

return inv_count;
}

/* Driver progra to test above functions */
int main(int argv, char** args)
{
int arr[] = {1, 20, 6, 4, 5};
printf(" Number of inversions are %d \n", getInvCount(arr, 5));
getchar();
return 0;
}

Time Complexity: O(n^2)

Method2 Using BST

#include
using namespace std;

struct node{
int data;
node *left;
node *right;
int rc;
};

node *root = NULL;

int get_inv(int val)
{
node *newnode = new node;
newnode -> data = val;
newnode -> left = NULL;
newnode -> right = NULL;
newnode -> rc = 0;

int inv = 0;

if(!root)
{
root = newnode;
return 0;
}

node *ptr = root;
node *pptr = root;
while(ptr)
{
pptr = ptr;
if(val < ptr->data)
{
inv += ptr->rc +1;
ptr = ptr->left;
}
else
{
ptr->rc++;
ptr = ptr->right;
}
}

if(val < pptr->data)
{
pptr->left = newnode;
}
else
{
pptr->right = newnode;
}

return inv;
}

int count_inv(int *array,int n)
{
int inv = 0;
for(int i=0;i {
inv += get_inv(array[i]);
}
return inv;
}

int main()
{
int array[] = {3,6,1,2,4,5};
cout< return 0;
}
Run Here https://ideone.com/Ghvop
Solution Provided by Naman
Time Complexity O(n(logn))