Array Sorting Binary Search Two Pointers
Proficient Level

Implement the mergeSortInversionCount method that counts inversions using merge-sort style processing.

The input contains an integer array nums and its length size. Your task is to count the number of inversions in the array.

An inversion is a pair of indexes i and j where i < j but nums[i] > nums[j]. It means a larger value appears before a smaller value.

For example, in [2,4,1,3,5], the inversion pairs are (2,1), (4,1), and (4,3), so the answer is 3.

Example 1
Input:
nums (int[]) = [2,4,1,3,5]
size (int) = 5
Return:
(int) 3
Example 2
Input:
nums (int[]) = [5,4,3,2,1]
size (int) = 5
Return:
(int) 10
Example 3
Input:
nums (int[]) = [1,2,3]
size (int) = 3
Return:
(int) 0

Use merge sort and count inversions while merging.

During the merge step, if the value from the left half is less than or equal to the value from the right half, it does not create new inversions. But if the right value is smaller, then it forms inversions with all remaining values in the left half.

Add those remaining left-side values to the count, then continue merging normally.

Pseudocode:

function mergeSortInversionCount(nums, size):
    return sortAndCount(nums, 0, size - 1)
function sortAndCount(nums, left, right):
    if left >= right:
        return 0
    mid = left + (right - left) / 2
    count = sortAndCount(nums, left, mid)
    count = count + sortAndCount(nums, mid + 1, right)
    count = count + mergeAndCount(nums, left, mid, right)
    return count
function mergeAndCount(nums, left, mid, right):
    count = 0
    merge both sorted halves
    when right value is smaller than left value:
        count = count + number of remaining values in left half
    return count
Run your code to see the result.