Given an array of integers A. If i < j and A[i] > A[j] then the pair (i, j) is called an inversion of A. Find the total number of inversions of A modulo (109 + 7). code example

Example: counting inversions

'''for counting pairs the best algo has time complexty O(n*log(n))'''

''' for collecting such pairs the best algo. has time complexity O(n*n)'''

PAIRS=0
def merge(left,right):
    global PAIRS
    length_1,length_2=len(left),len(right)
    index1,index2=0,0
    ans=[]
    for i in range(length_1+length_2):
        if index1==length_1:
            ans.append(right[index2])
            index2+=1
        elif index2==length_2:            
            ans.append(left[index1])
            index1+=1
        elif left[index1]<right[index2]:
            ans.append(left[index1])
            index1+=1
        else:
            ans.append(right[index2])
            PAIRS+=length_1-index1
            index2+=1
    return ans
def find_all_pairs(lst):
    pairs=[]
    for i in range(len(lst)):
        for j in range(i,len(lst)):
            if lst[i]>lst[j]:pairs.append((lst[j],lst[i]))
    return pairs
def memsort(lst):
    global PAIRS
    if len(lst)<3:
        if len(lst)==2:
            if lst[0]>lst[1]:
                lst[1],lst[0]=lst[0],lst[1]
                PAIRS+=1
    else:
        mid=len(lst)//2
        left=lst[:mid]
        right=lst[mid:]
        left=memsort(left)
        right=memsort(right)
        lst=merge(left,right)
    return lst
if __name__=='__main__':
    a=[int(i) for i in input('Enter the list of Numbers: ').split()]
    print(find_all_pairs(a)) # for priniting all pairs
    memsort(a)
    print(PAIRS) # for counting such pairs