Merging two sorted lists into a larger sorted list

Here's a version that uses the Python library heapq:

import heapq

def merge(aList, bList)
    return list(heapq.merge(aList, bList))

This isn't the most elegant of solutions however it does show all of the possible conditions and solves the problem at hand and should help provide an understanding of the logic of the merge operation.

def merge(a, b):
   newList = []
   while(len(a) > 0 or len(b) > 0):
      if( len(a) == 0 ):
         newList.append(b[0])
         b.pop(0)
      elif( len(b) == 0 ):
        newList.append(a[0])
         a.pop(0)
      elif( a[0] < b[0] ):
         newList.append(a[0])
         a.pop(0)
      else:
         newList.append(b[0])
         b.pop(0)
return newList

>>> merge([3,4,8,9], [1,2,5,8])

Make sure you keep adding elements even if a list is out of elements. Your current code stops once either aList or bList is empty, which is probably not what you want.

You can do this by using the fact that an empty list is evaluated as False using an if expression:

def merge(aList, bList):
    newList = []
    while (aList or bList): # single empty list won't stop the loop
        if not bList or (aList and aList[0] < bList[0]):
            # either bList is empty, or aList has next item
            newList.append(aList.pop(0))
        else:
            # bList has next item
            newList.append(bList.pop(0))
    reutrn newList

list1 = [3, 4, 8, 9]
list2 = [1, 2, 5, 8]

print(merge(list1, list2))
print(list1)
print(list2)

Output:

sh-4.2# python3 main.py                                                                              
[1, 2, 3, 4, 5, 8, 8, 9]                                                                             
[]                                                                                                   
[]