Question 2Counting inversions. An inversion in an array a[\,]a[] is a pair of entries a[i]a[i] and a[j]a[j] such that i < ji<j but a[i] > a[j]a[i]>a[j]. Given an array, design a linearithmic algorithm to count the number of inversions. 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]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