CODEWITHSUNDEEP
pythonlist
Tam211
Tam211

Reputation: 743

How to merge two sorted lists?

I'm supposed to write a code to merge sorted lists, I got an error in the second function which says:

TypeError: object of type 'NoneType' has no len()

my code is :

def merge(lst1, lst2):
    """ merging two ordered lists using
        the three pointer algorithm """
    n1 = len(lst1)
    n2 = len(lst2)
    lst3 = [0 for i in range(n1 + n2)]  # alocates a new list
    i = j = k = 0  # simultaneous assignment

    while (i < n1 and j < n2):
        if (lst1[i] <= lst2[j]):
            lst3[k] = lst1[i]
            i = i +1
        else:
            lst3[k] = lst2[j]
            j = j + 1
        k = k + 1  # incremented at each iteration
    lst3[k:] = lst1[i:] + lst2[j:]  # append remaining elements

def multi_merge_v3(lst_of_lsts):
     m = len(lst_of_lsts)
     merged = []
     for i in range(m):
          merged= merge((merged),(lst_of_lsts)[i])
     return(merged)

what does this error mean?

what should I fix in my code?

Upvotes: 0

Views: 1554

Answers (4)

Dan H
Dan H

Reputation: 14580

Here's another answer: use the "merge" function of heapq:

import heapq

merged = heapq.merge(lst1, lst2)

This is very efficient as merge expects lst1 and lst2 to already be sorted, so it only looks at the first element as it goes.

Note that merge also allow multiple (already sorted) arguments:

merged = heapq.merge(lst1, lst2, lst3, lst4)

At this point, merged is actually itself an iterator. To get an actual list, instead use:

merged = list(heapq.merge(lst1, lst2))

Remember: with Python, the "batteries are included".

Upvotes: 0

Dan H
Dan H

Reputation: 14580

Here's an option: rely on Python's built-in sorted function:

merged = sorted(lst1 + lst2)

Upvotes: 0

Anand Varma
Anand Varma

Reputation: 150

Here's a simple take on the sorted-list merging problem. 

l1 = [1,12,15,26,38]
l2 = [2,13,17,30,45,50]

# merged list
ml= [0]*(len(l1)+len(l2))


i1 = i2 = 0
for i in range(len(l1)+len(l2)): 
    if i1 == len(l1): 
        ml = ml[:i] + l2[i2:] 
        break
    if i2 == len(l2):
        ml = ml[:i] + l1[i1:]
        break       

    if l1[i1] < l2[i2]:
        ml[i] = l1[i1]
        i1 = i1 + 1
    else:
        ml[i] = l2[i2]
        i2 = i2 + 1 

print ml

Upvotes: 0

Ashwini Chaudhary
Ashwini Chaudhary

Reputation: 251166

You're not returning anything from function merge(), so by default it returns None that you assigned to merged. So, during the second call to merge() you'll be doing len(None).

 for i in range(m):
      #Assigning None here 
      merged = merge(merged, lst_of_lsts[i])
 return(merged)

So, at the end of that function:

return lst3

Upvotes: 2

Related Questions