Part 11 of 15 in Sorting  

Counting Inversions by phantom11

Problem statement

Given an array of N elements, you need to count the number of inversions in the array. An inversion is defined as a pair(i, j) such that i < j and A[i] > A[j]. For example in the array A[] = {3, 7, 4}, the pair (1, 2) is an inversion. This is because A[1] = 7 < A[2] = 4. There are no other inversions in the array.

Input & Output

The first line of the input contains the number of test cases T ( ≤ 10). Then T test cases follow. The first line of each test case contains the number of elements in the array N ( ≤ 105). The next line contains N space separated integers, which represent the array.

Note: Do not try to run nested for loops to compare every pair that exists. That will timeout. A better algorithm exists.

Sample Input
3 7 4
3 4 7
Sample Output
We can use the merge sort algorithm here. In the merge function, when we are merging two sorted sub arrays say Left (L) and Right (R), and lets say we are comparing the ith element of L with jth element of R, then if R[j] < L[i] we need to add len(L) - i + 1 to the answer.

To try out your code

Sign in

Sign up