Loading...
Loading...
Loading...
An inversion is a pair of positions i < j where the earlier number is larger than the later one. Count the inversions in a list in O(n log n) with a merge sort that counts while it merges.
Example
Input
5 3 1 2 5 4
Output
3
Pairs (3,1), (3,2) and (5,4).
Try the problem first. Open one hint at a time.
While merging, when a right-half item goes first, it is smaller than every item still left in the left half.
Add the length of the left leftovers to the count at that moment.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor