401. Count Inversions via Merge Sort

Given a linked list of integers, count the number of inversions — pairs of positions (i, j) with i < j but value at i greater than value at j. Use a merge-sort-based approach for O(n log n) time. The list is given as an array; return the inversion count.

Input: An array of node values.

Output: Integer — the number of inversions.

Examples

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

Input: [5,4,3,2,1]
Output: 10
Explanation: Fully reversed.

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

Constraints

• 0<=n<=10^5
• -10^9<=value<=10^9

Asked by