Search code examples
pythonalgorithmpython-3.xmergesort

What is the error in this merge sort implementation?

def merge(l1,l2):

  (lmerged,i,j) = ([],0,0)

  while i+j < len(l1) + len(l2):
    if i == len(l1):
      lmerged.append(l2[j])
      j = j+1
    elif j == len(l2):
      lmerged.append(l1[i])
      i = i+1
    elif l1[i] < l2[j]:
      lmerged.append(l1[i])
      i = i+1
    elif l2[j] < l1[i]:
      lmerged.append(l2[j])
      j = j+1
    else:
      lmerged.append(l1[i])
      i = i+1
      j = j+1

  return(lmerged)    

def mergesort(l):
  if len(l) < 2:
    return(l)
  else:
    n = len(l)
    leftsorted = mergesort(l[:n//2])
    rightsorted = mergesort(l[n//2:])
    return(merge(leftsorted,rightsorted))

What is the error in this code sample? On which list will this implementation fail? Is the logic correct or there is some flaw in my logic itself?

Solution

  • fail test: [1, 1] is sorted as [1]

    fix: remove j = j + 1 in merge function in the last else block.