Количество инверсий в массиве

GLOBAL_REPLACE_COUNT = 2
 
def merge(array: list, start: int, mid: int, end: int) -> None:
    
    global GLOBAL_REPLACE_COUNT
 
    l, m = 0, 0
    result = []
 
    while start + l < mid and m + mid < end:
        if array[start + l] <= array[mid + m]:
            result.append(array[start + l])
            l += 1
        else:
            result.append(array[mid + m])
            m += 1
           
 
    while start + l < mid:
        result.append(array[l + start])
        l += 1
 
    while m + mid < end:
        result.append(array[m + mid])
        m += 1
 
    for i in range(end - start):
        array[start + i] = result[i]
 
 
def merge_sort(array: list, start: int, end: int):
 
    if start + 1 < end:
        
        mid = int((start + end) / 2)
 
        ray, start, mid)
        
        merge_sort(array, mid, end)
        merge(array, start, mid, end)
        
        def main():
    
    length = int(input())
    array = list(map(int, input().split()))
    merge_sort(array, 0, len(array))
 
    print(GLOBAL_REPLACE_COUNT)
 
 
if __name__ == '__main__':
    main()

input('n = ')
arr = list(map(int, input('->').split()))
L = []
res = 0
for e in arr:
    if not L:
        L += [e]
    else:
        k = len(L)-1
        while k > -1 and e < L[k]:
            k -= 1
            res += 1
        if k == -1 or e > L[k]:
            L.insert(k+1,e)
        else:
            L.insert(k,e)
print(res)

from bisect import bisect_right
input('n = ')
arr = list(map(int, input('->').split()))
L = []
res = 0
for i in range(len(arr)):
    ind = bisect_right(L, arr[i])
    res += i-ind
    L.insert(ind, arr[i])
print(res)

from random import seed, shuffle
from time import perf_counter
 
def calc_inversion(a):
    if len(a) <= 1:
        return 0
    if len(set(a)) == 1:
        return 0
    avg_a = sum(a) / len(a)
    l, r = [], []
    addition = 0
    for x in a:
        if x < avg_a:
            l.append(x)
            addition += len(r)
        else:
            r.append(x)
    return addition + calc_inversion(l) + calc_inversion(r)  
 
n = 100000
seed(42)
a = list(range(n))
shuffle(a)
start = perf_counter()
print(calc_inversion(a))
print(perf_counter()-start)