Count Inversions (Merge Sort)

An inversion is a pair (i, j) such that i < j and nums[i] > nums[j]. Return the number of inversions in the array.

Function signature

func CountInversions(nums []int) int64

Example

nums = [2,4,1,3,5]
output = 3

Constraints

• 0 <= len(nums) <= 200000
• -1_000_000_000 <= nums[i] <= 1_000_000_000

Notes

• Use a merge-sort style divide-and-conquer to count cross inversions.