Number of Inversions in Merge Sort python

Question

I am trying to count the number of inversions inside a Merge Sort algorithm. I have not made many modifications except adding a counter for the condition to flip the values if the value on the right hand is smaller than the left. The code I am using is below and it even prints the right answer on pythontutor.com but also generates an error. What I am not able to understand is the source of the error. Will someone here be able to please explain what am i not seeing? My code is below along with the error:

def merge(left,right):
    result=[]
    i,j=0,0
    count=0
    while (i<len(left)) and (j<len(right)):
      if left[i]<right[j]:
          result.append(left[i])
          count+=1
          i+=1
      else:
          result.append(right[j])
          j+=1

    while (i<len(left)):
      result.append(left[i])
      i+=1

    while (j<len(right)):
      result.append(right[j])
      j+=1
   # print(count)
 return result,count

def merge_sort(list):
    if len(list)<2:
        return list
    else:
        middle=len(list)//2
        left=merge_sort(list[:middle])
        right=merge_sort(list[middle:])
        # return merge(left,right)
        result,count=merge(left,right)
        print(result,count)

merge_sort([2,3,9,2,9])

The error I am getting is:

TypeError: object of type 'NoneType' has no len()

Answer 1

Your issue is in the else block of your merge_sort function- you never return your list, so Python implicitly returns None. You want something like:

left,   left_count  = merge_sort(list[:middle])
right,  right_count = merge_sort(list[middle:])
result, merge_count = merge(left, right)

count = left_count + right_count + merge_count
return result, count

Aside: You shouldn't use builtin types (e.g. "list") as variable names, since they shadow the actual type.