Problem
An inversion is a pair of positions i < j with numbers[i] > numbers[j]. Count all inversions. Lists can be long, so a merge-sort based O(n log n) count is needed.
Implement count_inversions(numbers).
Input
numbers: The list of integers.
Output
Return the number of inversions.
Constraints
0 ≤ length ≤ 200,000
Examples
Input:
numbers = [2, 4, 1, 3, 5]
Expected output:
expected = 3Input:
std::vector<long long> numbers = {2, 4, 1, 3, 5};
Expected output:
long long expected = 3;Input:
long[] numbers = new long[] {2, 4, 1, 3, 5};
Expected output:
long expected = 3;Explanation
Out-of-order pairs: (2,1), (4,1), (4,3): 3 inversions.
Input:
numbers = [1, 2, 3]
Expected output:
expected = 0Input:
std::vector<long long> numbers = {1, 2, 3};
Expected output:
long long expected = 0;Input:
long[] numbers = new long[] {1, 2, 3};
Expected output:
long expected = 0;Explanation
Already sorted: 0 inversions.
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
An inversion is counted when a left-side number stays larger than a right-side number during merging.
Hint 2
Split the list recursively and count cross-pairs while merging sorted halves.
Hint 3
Be careful with duplicates: equal values are not inversions, so the comparison direction matters.
Expected complexity
O(n log n) time, O(n) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.