Array Sorting Merge Sort
Proficient Level

Implement the countInversionsInArray method that counts pairs that are out of sorted order in the array.

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 such that i < j and nums[i] > nums[j]. For example, in [2,4,1,3,5], the inversions 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]
size (int) = 3
Return:
(int) 3
Example 3
Input:
nums (int[]) = [1,2,3]
size (int) = 3
Return:
(int) 0

The direct way is to check every pair of elements where the first index comes before the second index.

If the earlier value is greater than the later value, that pair is an inversion. Increase the count for each such pair.

This method is easy to understand and works correctly for the given input format.

Pseudocode:

function countInversionsInArray(nums, size):
    count = 0
    for i from 0 to size - 1:
        for j from i + 1 to size - 1:
            if nums[i] > nums[j]:
                count++
    return count
Run your code to see the result.