Merging two sorted lists into a larger sorted list

Question

I'm trying to make a merge function that will be used in the merge sort that I'm making.

I have run into some trouble, and I can't seem to find the error.

I commented it to try to show you guys my thought process:

def merge(aList, bList):
    newList = []
    while (len(aList) > 0) & (len(bList) > 0):  #Loop until both lists are empty
        if aList[0] < bList[0]:         #If the first item of aList is smaller than the first item of bList
            newList.append(aList[0])    #add that item to the new list
            aList.pop(0)                #and remove it from the original list

        else:                           #If it gets here, that means the first item of bList was smaller
            newList.append(bList[0])    #So put the first item of bList is the new list
            bList.pop(0)                #and remove it from the original
    return newList

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

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

Output:

[1, 2, 3, 4, 5, 8]
[8, 9]
[0]

I was expecting list1 and list2 to be empty, but for some reason there appears to be an un-placed 8 and 9 in list1. Anyone have ideas?

Answer 1

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

import heapq

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