123. Count Inversions in Array

Given an integer array, count the number of inversions — pairs (i,j) with i<j and nums[i]>nums[j]. Use a merge-sort based approach for O(n log n).

Input: An integer array.

Output: Integer — inversion count.

Examples

Example 1

Input: [2,4,1,3,5]
Output: 3
Explanation: Inversions: (2,1),(4,1),(4,3).

Example 2

Input: [1,2,3]
Output: 0
Explanation: Already sorted.

Example 3

Input: [3,2,1]
Output: 3
Explanation: All pairs inverted.