Number of inversions using merge sort

Question

I wrote this code to get the number of inversions using merge_sort, but I am not getting the correct output. Can someone tell me why is it giving the wrong output?

def merge(B,C):  # B,C are sorted
  D = list()
  count = 0
  # empty list to get the merged list
  while (B != []) and (C != []):  # breaks if any one of B or C becomes empty

    b = B[0]  # to get first element of B
    print("b",b)
    c = C[0]  # to get first element of C
    print("c",c)
    
    if b<=c:
      B.remove(b)  # if bc remove c from C and add to D
      D.append(c)
      count += 1
      print("count_in_merge",count)

  # now if either one of B or C has become empty so while loop is exited
  # so we can add remaining elements of B and C as it is to D as they are
  # already sorted
  if B != []:                                       
    for i in B:
      D.append(i)
  
  if C != []:
     for i in C:
      D.append(i)

  return D, count 

def sort_and_num(A):
  if len(A) == 1:
    return A,0

  m = len(A) // 2
    
  B,count_b = sort_and_num(A[0:m])
  C,count_c = sort_and_num(A[m:])
    
  A_,count = merge(B,C)
  count += (count_b + count_c)
  
  return A_, count

When I run:

A = [ 9, 8 ,7, 3, 2, 1] 
A_,c = sort_and_num(A)
print(A_,c)

The output is:

[1, 2, 3, 7, 8, 9] 9

But the output should have been

[1, 2, 3, 7, 8, 9] 15

On the other hand, if I input :

A = [3,1,2,4] 
A_, count = sort_and_num(A)
print(A_, count)

the output is:

[1,2,3,4 ] 3

which is correct. Where is it going wrong?

user_844416 · Answer

In this code fragment:

else:
    C.remove(c)  # if b>c remove c from C and add to D
    D.append(c)
    count += 1

you should update count by length of the rest part of B list

    count += len(B)

because moving an element from the right part may "correct" many inversions at once.

Also note that chosen implementation is rather ineffective due to instant removing elements from the lists.

user_4593267 · Answer

There are some issues in your code:

to remove the first element of a list, you should use pop(), not remove()
the number of inversions when you take the element from C is len(B), not 1.
you should add the number of inversions from each half and that of the merge phase
the intial test in sort_and_num should also test for an empty list and return it with a count of 0.

Here is a modified version:

def merge(B, count_b, C, count_c):  # B,C are sorted
   D = []
   count = count_b + count_c
   # empty list to get the merged list
   while (B != []) and (C != []):  # breaks if any one of B or C becomes empty
      if B[0] <= C[0]:
         D.append(B.pop())  # if b<=c remove b from B and add it to D
      else:
         D.append(C.pop())  # if b>c remove c from C and add it to D
         count += len(B)    # moving c before all remaining elements of B

  # now if either one of B or C has become empty so while loop is exited
  # so we can add remaining elements of B and C as it is to D as they are
  # already sorted
  for i in B:
     D.append(i)
  
  for i in C:
     D.append(i)

  return D, count 

def sort_and_num(A):
   if len(A) <= 1:
      return A,0

   m = len(A) // 2
    
   B,count_b = sort_and_num(A[:m])
   C,count_c = sort_and_num(A[m:])
    
   return merge(B, count_b, C, count_c)

Number of inversions using merge sort

2 Answers