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:
33 3 1 73 8 4 24 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:
132
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:
Hint 2:
Hint 3:
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.