Combining two sorted lists in Python

is there a smarter way to do this in Python

This hasn't been mentioned, so I'll go ahead - there is a merge stdlib function in the heapq module of python 2.6+. If all you're looking to do is getting things done, this might be a better idea. Of course, if you want to implement your own, the merge of merge-sort is the way to go.

>>> list1 = [1, 5, 8, 10, 50]
>>> list2 = [3, 4, 29, 41, 45, 49]
>>> from heapq import merge
>>> list(merge(list1, list2))
[1, 3, 4, 5, 8, 10, 29, 41, 45, 49, 50]

Here's the documentation.

Long story short, unless len(l1 + l2) ~ 1000000 use:

L = l1 + l2
L.sort()

Description of the figure and source code can be found here.

The figure was generated by the following command:

$ python make-figures.py --nsublists 2 --maxn=0x100000 -s merge_funcs.merge_26 -s merge_funcs.sort_builtin

This is simply merging. Treat each list as if it were a stack, and continuously pop the smaller of the two stack heads, adding the item to the result list, until one of the stacks is empty. Then add all remaining items to the resulting list.

res = []
while l1 and l2:
    if l1[0] < l2[0]:
        res.append(l1.pop(0))
    else:
        res.append(l2.pop(0))

res += l1
res += l2

There is a slight flaw in ghoseb's solution, making it O(n**2), rather than O(n).
The problem is that this is performing:

item = l1.pop(0)

With linked lists or deques this would be an O(1) operation, so wouldn't affect complexity, but since python lists are implemented as vectors, this copies the rest of the elements of l1 one space left, an O(n) operation. Since this is done each pass through the list, it turns an O(n) algorithm into an O(n**2) one. This can be corrected by using a method that doesn't alter the source lists, but just keeps track of the current position.

I've tried out benchmarking a corrected algorithm vs a simple sorted(l1+l2) as suggested by dbr

def merge(l1,l2):
    if not l1:  return list(l2)
    if not l2:  return list(l1)

    # l2 will contain last element.
    if l1[-1] > l2[-1]:
        l1,l2 = l2,l1

    it = iter(l2)
    y = it.next()
    result = []

    for x in l1:
        while y < x:
            result.append(y)
            y = it.next()
        result.append(x)
    result.append(y)
    result.extend(it)
    return result

I've tested these with lists generated with

l1 = sorted([random.random() for i in range(NITEMS)])
l2 = sorted([random.random() for i in range(NITEMS)])

For various sizes of list, I get the following timings (repeating 100 times):

# items:  1000   10000 100000 1000000
merge  :  0.079  0.798 9.763  109.044 
sort   :  0.020  0.217 5.948  106.882

So in fact, it looks like dbr is right, just using sorted() is preferable unless you're expecting very large lists, though it does have worse algorithmic complexity. The break even point being at around a million items in each source list (2 million total).

One advantage of the merge approach though is that it is trivial to rewrite as a generator, which will use substantially less memory (no need for an intermediate list).

[Edit] I've retried this with a situation closer to the question - using a list of objects containing a field "date" which is a datetime object. The above algorithm was changed to compare against .date instead, and the sort method was changed to:

return sorted(l1 + l2, key=operator.attrgetter('date'))

This does change things a bit. The comparison being more expensive means that the number we perform becomes more important, relative to the constant-time speed of the implementation. This means merge makes up lost ground, surpassing the sort() method at 100,000 items instead. Comparing based on an even more complex object (large strings or lists for instance) would likely shift this balance even more.

# items:  1000   10000 100000  1000000[1]
merge  :  0.161  2.034 23.370  253.68
sort   :  0.111  1.523 25.223  313.20

[1]: Note: I actually only did 10 repeats for 1,000,000 items and scaled up accordingly as it was pretty slow.

This is simple merging of two sorted lists. Take a look at the sample code below which merges two sorted lists of integers.

#!/usr/bin/env python
## merge.py -- Merge two sorted lists -*- Python -*-
## Time-stamp: "2009-01-21 14:02:57 ghoseb"

l1 = [1, 3, 4, 7]
l2 = [0, 2, 5, 6, 8, 9]

def merge_sorted_lists(l1, l2):
    """Merge sort two sorted lists

    Arguments:
    - `l1`: First sorted list
    - `l2`: Second sorted list
    """
    sorted_list = []

    # Copy both the args to make sure the original lists are not
    # modified
    l1 = l1[:]
    l2 = l2[:]

    while (l1 and l2):
        if (l1[0] <= l2[0]): # Compare both heads
            item = l1.pop(0) # Pop from the head
            sorted_list.append(item)
        else:
            item = l2.pop(0)
            sorted_list.append(item)

    # Add the remaining of the lists
    sorted_list.extend(l1 if l1 else l2)

    return sorted_list

if __name__ == '__main__':
    print merge_sorted_lists(l1, l2)

This should work fine with datetime objects. Hope this helps.

from datetime import datetime
from itertools import chain
from operator import attrgetter

class DT:
    def __init__(self, dt):
        self.dt = dt

list1 = [DT(datetime(2008, 12, 5, 2)),
         DT(datetime(2009, 1, 1, 13)),
         DT(datetime(2009, 1, 3, 5))]

list2 = [DT(datetime(2008, 12, 31, 23)),
         DT(datetime(2009, 1, 2, 12)),
         DT(datetime(2009, 1, 4, 15))]

list3 = sorted(chain(list1, list2), key=attrgetter('dt'))
for item in list3:
    print item.dt

The output:

2008-12-05 02:00:00
2008-12-31 23:00:00
2009-01-01 13:00:00
2009-01-02 12:00:00
2009-01-03 05:00:00
2009-01-04 15:00:00

I bet this is faster than any of the fancy pure-Python merge algorithms, even for large data. Python 2.6's heapq.merge is a whole another story.

def merge_sort(a,b):

    pa = 0
    pb = 0
    result = []

    while pa < len(a) and pb < len(b):
        if a[pa] <= b[pb]:
            result.append(a[pa])
            pa += 1
        else:
            result.append(b[pb])
            pb += 1

    remained = a[pa:] + b[pb:]
    result.extend(remained)


return result

Python's sort implementation "timsort" is specifically optimized for lists that contain ordered sections. Plus, it's written in C.

http://bugs.python.org/file4451/timsort.txt
http://en.wikipedia.org/wiki/Timsort

As people have mentioned, it may call the comparison function more times by some constant factor (but maybe call it more times in a shorter period in many cases!).

I would never rely on this, however. – Daniel Nadasi

I believe the Python developers are committed to keeping timsort, or at least keeping a sort that's O(n) in this case.

Generalized sorting (i.e. leaving apart radix sorts from limited value domains)
cannot be done in less than O(n log n) on a serial machine. – Barry Kelly

Right, sorting in the general case can't be faster than that. But since O() is an upper bound, timsort being O(n log n) on arbitrary input doesn't contradict its being O(n) given sorted(L1) + sorted(L2).

An implementation of the merging step in Merge Sort that iterates through both lists:

def merge_lists(L1, L2):
    """
    L1, L2: sorted lists of numbers, one of them could be empty.

    returns a merged and sorted list of L1 and L2.
    """

    # When one of them is an empty list, returns the other list
    if not L1:
        return L2
    elif not L2:
        return L1

    result = []
    i = 0
    j = 0

    for k in range(len(L1) + len(L2)):
        if L1[i] <= L2[j]:
            result.append(L1[i])
            if i < len(L1) - 1:
                i += 1
            else:
                result += L2[j:]  # When the last element in L1 is reached,
                break             # append the rest of L2 to result.
        else:
            result.append(L2[j])
            if j < len(L2) - 1:
                j += 1
            else:
                result += L1[i:]  # When the last element in L2 is reached,
                break             # append the rest of L1 to result.

    return result

L1 = [1, 3, 5]
L2 = [2, 4, 6, 8]
merge_lists(L1, L2)               # Should return [1, 2, 3, 4, 5, 6, 8]
merge_lists([], L1)               # Should return [1, 3, 5]

I'm still learning about algorithms, please let me know if the code could be improved in any aspect, your feedback is appreciated, thanks!

Use the 'merge' step of merge sort, it runs in O(n) time.

From wikipedia (pseudo-code):

function merge(left,right)
    var list result
    while length(left) > 0 and length(right) > 0
        if first(left) ≤ first(right)
            append first(left) to result
            left = rest(left)
        else
            append first(right) to result
            right = rest(right)
    end while
    while length(left) > 0 
        append left to result
    while length(right) > 0 
        append right to result
    return result

Recursive implementation is below. Average performance is O(n).

def merge_sorted_lists(A, B, sorted_list = None):
    if sorted_list == None:
        sorted_list = []

    slice_index = 0
    for element in A:
        if element <= B[0]:
            sorted_list.append(element)
            slice_index += 1
        else:
            return merge_sorted_lists(B, A[slice_index:], sorted_list)

    return sorted_list + B

or generator with improved space complexity:

def merge_sorted_lists_as_generator(A, B):
    slice_index = 0
    for element in A:
        if element <= B[0]:
            slice_index += 1
            yield element       
        else:
            for sorted_element in merge_sorted_lists_as_generator(B, A[slice_index:]):
                yield sorted_element
            return        

    for element in B:
        yield element

This is my solution in linear time without editing l1 and l2:

def merge(l1, l2):
  m, m2 = len(l1), len(l2)
  newList = []
  l, r = 0, 0
  while l < m and r < m2:
    if l1[l] < l2[r]:
      newList.append(l1[l])
      l += 1
    else:
      newList.append(l2[r])
      r += 1
  return newList + l1[l:] + l2[r:]

I'd go with the following answer.

from math import floor

def merge_sort(l):
    if len(l) < 2:
        return l
    left = merge_sort(l[:floor(len(l)/2)])
    right = merge_sort(l[floor(len(l)/2):])
    return merge(left, right)

def merge(a, b):
    i, j = 0, 0
    a_len, b_len = len(a), len(b)
    output_length = a_len + b_len
    out = list()
    for _ in range(output_length):
        if i < a_len and j < b_len and a[i] < b[j]:
            out.append(a[i])
            i = i + 1
        elif j < b_len:
            out.append(b[j])
            j = j + 1
    
    while (i < a_len):
        out.append(a[i])
        i += 1
    
    while (j < b_len):
        out.append(b[j])
        j += 1
        
    return out


if __name__ == '__main__':
    print(merge_sort([7, 8, 9, 4, 5, 6]))

Well, the naive approach (combine 2 lists into large one and sort) will be O(N*log(N)) complexity. On the other hand, if you implement the merge manually (i do not know about any ready code in python libs for this, but i'm no expert) the complexity will be O(N), which is clearly faster. The idea is described wery well in post by Barry Kelly.

If you want to do it in a manner more consistent with learning what goes on in the iteration try this

def merge_arrays(a, b):
    l= []

    while len(a) > 0 and len(b)>0:
        if a[0] < b[0]: l.append(a.pop(0))    
        else:l.append(b.pop(0))

    l.extend(a+b)
    print( l )

import random

    n=int(input("Enter size of table 1")); #size of list 1
    m=int(input("Enter size of table 2")); # size of list 2
    tb1=[random.randrange(1,101,1) for _ in range(n)] # filling the list with random
    tb2=[random.randrange(1,101,1) for _ in range(m)] # numbers between 1 and 100
    tb1.sort(); #sort the list 1 
    tb2.sort(); # sort the list 2
    fus=[]; # creat an empty list
    print(tb1); # print the list 1
    print('------------------------------------');
    print(tb2); # print the list 2
    print('------------------------------------');
    i=0;j=0;  # varialbles to cross the list
    while(i<n and j<m):
        if(tb1[i]<tb2[j]):
            fus.append(tb1[i]); 
            i+=1;
        else:
            fus.append(tb2[j]);
            j+=1;

    if(i<n):
        fus+=tb1[i:n];
    if(j<m):
        fus+=tb2[j:m];

    print(fus);

  # this code is used to merge two sorted lists in one sorted list (FUS) without
  #sorting the (FUS)

Have used merge step of the merge sort. But I have used generators. Time complexity O(n)

def merge(lst1,lst2):
    len1=len(lst1)
    len2=len(lst2)
    i,j=0,0
    while(i<len1 and j<len2):
        if(lst1[i]<lst2[j]):
                yield lst1[i]
                i+=1
        else:
                yield lst2[j]
                j+=1
    if(i==len1):
        while(j<len2):
                yield lst2[j]
                j+=1
    elif(j==len2):
        while(i<len1):
                yield lst1[i]
                i+=1
l1=[1,3,5,7]
l2=[2,4,6,8,9]
mergelst=(val for val in merge(l1,l2))
print(*mergelst)

This code has time complexity O(n) and can merge lists of any data type, given a quantifying function as the parameter func. It produces a new merged list and does not modify either of the lists passed as arguments.

def merge_sorted_lists(listA,listB,func):
    merged = list()
    iA = 0
    iB = 0
    while True:
        hasA = iA < len(listA)
        hasB = iB < len(listB)
        if not hasA and not hasB:
            break
        valA = None if not hasA else listA[iA]
        valB = None if not hasB else listB[iB]
        a = None if not hasA else func(valA)
        b = None if not hasB else func(valB)
        if (not hasB or a<b) and hasA:
            merged.append(valA)
            iA += 1
        elif hasB:
            merged.append(valB)
            iB += 1
    return merged

in O(m+n) complexity

def merge_sorted_list(nums1: list, nums2:list) -> list:
        m = len(nums1)
        n = len(nums2)
        
        nums1 = nums1.copy()
        nums2 = nums2.copy()
        nums1.extend([0 for i in range(n)])
        while m > 0 and n > 0:
            if nums1[m-1] >= nums2[n-1]:
                nums1[m+n-1] = nums1[m-1]
                m -= 1
            else:
                nums1[m+n-1] = nums2[n-1]
                n -= 1
        if n > 0:
            nums1[:n] = nums2[:n]
        return nums1

l1 = [1, 3, 4, 7]    
l2 =  [0, 2, 5, 6, 8, 9]    
print(merge_sorted_list(l1, l2))

output

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

def compareDate(obj1, obj2):
    if obj1.getDate() < obj2.getDate():
        return -1
    elif obj1.getDate() > obj2.getDate():
        return 1
    else:
        return 0



list = list1 + list2
list.sort(compareDate)

Will sort the list in place. Define your own function for comparing two objects, and pass that function into the built in sort function.

Do NOT use bubble sort, it has horrible performance.