Title

Number of Inversions in an array

Inversion: i < j and arr[i] > arr[j]

from typing import List
class Solution:
    def countInversions(self, nums: List[int]) -> int:
        invCount = 0
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)-1):
                if nums[i] > nums[j]:
                    print("({},{})".format(nums[i], nums[j]))
                    invCount += 1
        
        return invCount

sol = Solution()
sol.countInversions([2, 5, 1, 7, 9])

(2,1)
(5,1)

2

def mergeSort(arr):
    mid = len(arr)//2
    leftArr = arr[:mid]
    rightArr = arr[mid:]
    
    mergeSort(leftArr)
    mergeSort(rightArr)