Count Inversions With Merge Sort
Problem statement
You are given an integer array nums. An inversion is a pair of positions i < j where nums[i] > nums[j]: a larger value that comes before a smaller one.
Return the number of inversions. Two equal values never form an inversion.
Function
countInversions(nums: int[]) → longExamples
Example 1
nums = [4,1,3,2]return = 4The pairs out of order are (4, 1), (4, 3), (4, 2) and (3, 2): 4 in total. The pair (1, 3) and the pair (1, 2) are already in order.
Example 2
nums = [5,5,2]return = 2Each 5 comes before the smaller 2, which gives 2 inversions. The two 5s are equal, so they are not an inversion.
Example 3
nums = [-1,0,7]return = 0The values already go up, so no pair is out of order.
Constraints
1 <= nums.length <= 10^4-10^5 <= nums[i] <= 10^5