Как найти инверсию counting с помощью mergesort в Python?

Question

Это моя программа для поиска инверсии counting в алгоритме mergesort, хотя я не могу найти правильное значение инверсии. Может кто-нибудь, пожалуйста, скажите мне, где я ошибаюсь?

import time 
import random 
start=time.time() 

def merge_sort(items): 
    """ Implementation of mergesort """ 
    count=0 
    if len(items) > 1: 

     mid = len(items) // 2  # Determine the midpoint and split 
     left = items[0:mid] 
     right = items[mid:] 

     merge_sort(left)   # Sort left list in-place 
     merge_sort(right)   # Sort right list in-place 

     l, r = 0, 0 
     for i in range(len(items)):  # Merging the left and right list 

      lval = left[l] if l < len(left) else None 
      rval = right[r] if r < len(right) else None 

      if (lval is not None and rval is not None and lval < rval) or rval is None: 
       items[i] = lval 
       l += 1 
      elif (lval is not None and rval is not None and lval >= rval) or lval is None: 
       items[i] = rval 
       count=count+(len(items)-l) 
       r += 1 

     print(count)   
    return items 

#n=int(input("enter number of elements in list")) 
items=[2,1,5,4,3,9] 
#for x in range (n): 

# items.append(random.random()) 


print(merge_sort(items)) 
print("time is %s"%(time.time()-start)) 

Answer 1

Здесь вы можете вычислить количество инверсий в списке чисел.

def count_inversions(items): 
    inversions = 0 
    for idx, item in enumerate(items): 
     if idx < len(items) - 1 and items[idx] > items[idx + 1]: 
      inversions += 1 
    return inversions 

Необходимо называть это один раз. Он идет выше любых рекурсивных вызовов (слева и справа).