Got wrong answer in implementing merge sort in python

Question

I am getting wrong answer for particular input arrays in this merge sort implementation.

I tried with this code below in python.

Python code -

a=[100,3,4]
b=[]
for i in range(len(a)):
  b.append(0)



def ms( a ,lb,ub ):
  if (lb<ub):
    mid=int((lb+ub)/2)
    ms(a, lb, mid)
    ms(a, mid+1,ub)
    merge(a,lb,mid,ub)

def merge(a,lb,mid,ub):
  i=lb
  j=mid+1
  k=lb

  while (i<=mid and j<=ub) :
    if a[i]<=a[j]:
      b[k]=a[i]
      i+=1
      k+=1
    else:
      b[k]=a[j]
      j+=1
      k+=1
  if (i>mid) :
    while j<=ub :
      b[k]=a[j]
      j+=1
      k+=1
  elif (j>ub) :
    while i<=mid :
      b[k]=a[i]
      i+=1
      k+=1

ms(a,0 , len(a)-1)
print(b)

i am getting output wrong answer. Please go through this.

Answer 1

There are several problems with this code. You don't ask for a fix, and I can imagine at least two ways to go about fixing it, so I'll leave it to you, but essentially the fundamental problem in your implementation is that you're merging into b twice, both times at the beginning. That overwrites what the first one does.

If you add a print statement right before ms calls merge, you'll see that one call to ms turns b into the list [3, 0, 0], and a second call turns it into the list [4, 100, 0]. In other words, you've lost information. This happens because merge always initializes k=lb.

IMHO you should not try to perform merge sort using a global list in this manner.