CODEWITHSUNDEEP
pythonsorting
Joey Weidman
Joey Weidman

Reputation: 403

Merging two sorted lists into a larger sorted list

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?

Upvotes: 6

Views: 2795

Answers (5)

Jason Angel
Jason Angel

Reputation: 2444

This alternative follows @Reut Sharabani idea about handle empty lists but I simply decided to pop the smallest numbers until empty anyone and add the other (remaining) to the end.

def merge_sorted_lists(list1,list2):
    new_sorted = []

    # select the smallest number in current lists until empty any list
    while len(list1 and list2):    
        toadd = list1.pop(0) if (list1[0]<=list2[0])  else list2.pop(0) # select the smaller number
        new_sorted.append(toadd)

    remaining = list1 if (not list2) else list2
    new_sorted += remaining # the remaining is always greater and sorted
    return new_sorted

list1, list2 = [35, 36, 46, 82, 92], [0, 11, 15, 22, 22, 33, 35, 53, 59, 61, 74, 76]
print(merge_sorted_lists(list1,list2))

Upvotes: 0

Ugur Yilmaz
Ugur Yilmaz

Reputation: 499

Not the best solution but I encountered to same problem today;

def merge(str1, str2):
j = 0
for i in range(len(str2)):
    while(j < len(str1) and str2[i] > str1[j]):
        j += 1
    str1.insert(j, str2[i])
return str1

Upvotes: 0

Reut Sharabani
Reut Sharabani

Reputation: 31349

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]                                                                             
[]                                                                                                   
[]

Upvotes: 2

Brian Cain
Brian Cain

Reputation: 966

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])

Upvotes: 3

Brent Washburne
Brent Washburne

Reputation: 13158

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

import heapq

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

Upvotes: 5

Related Questions