Count inversions

'''

Brute Force; Two loops- i(0:n-2) & j(i+1:n-1) if arr[j] element is smaller than arr[i], increment the ans.No need to swap. Time complexity O(N^2)

T.C O(nlogn) S.C O(n)
logic:
*We want pair of elements where first element should be greater and second should be smaller.
*We applied merge sort but while merging two sorted arrays,if left array ie. arr1 ith
 element which is greater than jth element of right array ie. arr2 then all the elements
 after ith element including ith element will be greater than jth element of arr2 because
 both array is sorted so that satisfies our condition so we will add that in answer.

###None of the merge sort function returns any array or anything else.
'''

def merge(arr,l,mid,r,ans):
    final_arr=[]
    i,j=l,mid+1

    '''
    First thing you should understand both left and right table will be sorted in ascending order for sure at this step.
    so for eg. left arr=[2,5,8,12] and right_arr=[3,6,9] so after pushing 2 into the final array, when 3 comes which is smaller than [5,8,12] so
    our answer should increase by (mid-i+1) where i points ot 5 so mid-i+1 is all the remaining elments of the left array because if kth elmenet is bigger than
    3(from right array of our example) then all the elments of the left array will be bigger only as both array are sorted.
    '''
    while i<=mid and j<=r:
        if arr[i]<=arr[j]:
            final_arr.append(arr[i])
            i+=1
        else:
            '''Here jth element which is greater than all the elmenets of '''
            final_arr.append(arr[j])
            ans[0]+=(mid-i+1)
            j+=1
    if j>r:
        while i<=mid:
            final_arr.append(arr[i])
            i+=1
    elif i>mid:
        while j<=r:
            final_arr.append(arr[j])
            ans[0]+=(mid-i+1)
            j+=1
    arr[l:r+1] = final_arr



def mergesort(arr,i,j,ans):
    if i<j:
        mid= (i+j)//2
        mergesort(arr,i,mid,ans)
        mergesort(arr,mid+1,j,ans)
        merge(arr,i,mid,j,ans)

class Solution:
    def inversionCount(self, arr):
        ans=[0]
        mergesort(arr,0,len(arr)-1,ans)
        return ans[0]