Now that we have seen merge-sort and implemented it, it’s time to solve a challenging problem using merge-sort. You can work in any programming language of your choice - Python, C++, Java, or anything else you want. Let’s get started!

Problem Statement

We’re given an array of numbers, and we need to count the total number of inversions in the array. An inversion occurs when two numbers are out of order in the array, i.e. a number on the left is larger than a number on the right. More formally, an inversion occurs when array[i] > array[j] and i < j. We need to count the total number of pairs (i, j) for which there is an inversion in the array.

Constraints: $n \leq 1000000$. Desired solution has complexity O($n \log n$).

IO description

Input description: The first line contains the number of test cases T. Each test case is on a separate line. The first number is $n$, denoting the length of the array. This is followed by $n$ numbers describing the array.

Sample Input:

3
3 3 1 7
3 8 4 2
4 5 1 7 5

Output description: Output should contain T lines. Each line should contain the answer for the respective test case, the number of inversions.

Sample output:

1
3
2

Explanation:

In the first test case, the only pair of numbers that are out of order are 3 and 1 (for i = 0 and j = 1).

In the second test case, every pair of numbers is an inversion - (8, 4), (4, 2) and (8, 2).

Submitting your solution

Once you are confidant of your solution, download the input file and run your code with the provided input. Then take the quiz!

Progressive ‘hint-by-hint’ solution

Only look at the hints if you can’t solve the problem for at-least 20-minutes. Read only one hint that you could not figure out on your own. Then spend at-least 20-minutes trying to solve the problem again.

Hint 1:

We just learnt about sorting arrays. What is the relation between sorting an array and counting inversions?

Hint 2:

Sorting an array gets rid of inversions. Now let’s see what is the relation between merge-sort and counting inversions. Does merge-sort even introduce new inversions? Does it get rid on inversions? When?

Hint 3:

Merge-sort never introduces new inversions. It gets rid on inversions during the merge step. The merge step is best place to count the number of inversions.

Full solution

The solution for this assignment is included at the end of the quiz. The code executes within 10.00 seconds. If you implemented your solution in C++ or Java, you should expect your solution to run at-least 5x faster.