Merge sorted lists in python

I like Roberto Liffredo's answer. I didn't know about heapq.merge(). Hmmmph.

Here's what the complete solution looks like using Roberto's lead:

class Obj(object):
    def __init__(self, p) :
        self.points = p
    def __cmp__(self, b) :
        return cmp(self.points, b.points)
    def __str__(self):
        return "%d" % self.points

a = [Obj(1), Obj(3), Obj(8)]
b = [Obj(1), Obj(2), Obj(3)]
c = [Obj(100), Obj(300), Obj(800)]

import heapq

sorted = [item for item in heapq.merge(a,b,c)]
for item in sorted:
    print item

Or:

for item in heapq.merge(a,b,c):
    print item

Use the bisect module. From the documentation: "This module provides support for maintaining a list in sorted order without having to sort the list after each insertion."

import bisect

def magic(*args):
    r = []
    for a in args:
        for i in a:
            bisect.insort(r, i)
    return r

Instead of using a list, you can use a [heap](http://en.wikipedia.org/wiki/Heap_(data_structure).

The insertion is O(log(n)), so merging a, b and c will be O(n log(n))

In Python, you can use the heapq module.

I don't know whether it would be any quicker, but you could simplify it with:

def GetObjKey(a):
    return a.points

return sorted(a + b + c, key=GetObjKey)

You could also, of course, use cmp rather than key if you prefer.

One line solution using sorted:

def magic(*args):
  return sorted(sum(args,[]), key: lambda x: x.points)

IMO this solution is very readable.

Using heapq module, it could be more efficient, but I have not tested it. You cannot specify cmp/key function in heapq, so you have to implement Obj to be implicitly sorted.

import heapq
def magic(*args):
  h = []
  for a in args:
    heapq.heappush(h,a)
  return [i for i in heapq.heappop(h)

I asked a similar question and got some excellent answers:

• Joining a set of ordered-integer yielding Python iterators

The best solutions from that question are variants of the merge algorithm, which you can read about here:

• Wikipedia: Merge Algorithm

Below is an example of a function that runs in O(n) comparisons.

You could make this faster by making a and b iterators and incrementing them.

I have simply called the function twice to merge 3 lists:

def zip_sorted(a, b):
    '''
    zips two iterables, assuming they are already sorted
    '''
    i = 0
    j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    if i < len(a):
        result.extend(a[i:])
    else:
        result.extend(b[j:])
    return result

def genSortedList(num,seed):
    result = [] 
    for i in range(num):
        result.append(i*seed)
    return result

if __name__ == '__main__':
    a = genSortedList(10000,2.0)
    b = genSortedList(6666,3.0)
    c = genSortedList(5000,4.0)
    d = zip_sorted(zip_sorted(a,b),c)
    print d

However, heapq.merge uses a mix of this method and heaping the current elements of all lists, so should perform much better

Here you go: a fully functioning merge sort for lists (adapted from my sort here):

def merge(*args):
    import copy
    def merge_lists(left, right):
        result = []
        while left and right:
            which_list = (left if left[0] <= right[0] else right)
            result.append(which_list.pop(0))
        return result + left + right
    lists = list(args)
    while len(lists) > 1:
        left, right = copy.copy(lists.pop(0)), copy.copy(lists.pop(0))
        result = merge_lists(left, right)
        lists.append(result)
    return lists.pop(0)

Call it like this:

merged_list = merge(a, b, c)
for item in merged_list:
    print item

For good measure, I'll throw in a couple of changes to your Obj class:

class Obj(object):
    def __init__(self, p) :
        self.points = p
    def __cmp__(self, b) :
        return cmp(self.points, b.points)
    def __str__(self):
        return "%d" % self.points

• Derive from object
• Pass self to __init__()
• Make __cmp__ a member function
• Add a str() member function to present Obj as string

Here is your magic function, in O(n0+n1+n2+...).

It tracks a pointer for each iterable and yields the smallest item at any pointer. i.e. Same idea as the 'merge' part of mergesort.

def merge(*iterables, key=lambda x:x):
    L = len(iterables)
    ls = [len(l) for l in iterables]
    ps = [0] * len(iterables)
    while sum([ls[i] - ps[i] for i in range(0, L)]) > 0:
        min, mink = None, None
        mini = -1
        for i in range(0, L):  # loop over pointers
            if ps[i] == ls[i]: continue
            keyed = key(iterables[i][ps[i]])
            if mink is None or keyed < mink:
                min = iterables[i][ps[i]]
                mink = keyed
                mini = i
        yield min
        ps[mini] += 1

Usage is:

merge([1, 2, 3], [3, 4, 5], [2, 4, 10]) == [1, 2, 2, 3, 3, 4, 4, 5, 10]

Note: It takes a key function, but the input iterables must also have been sorted according to the same key otherwise the inputs are not properly sorted.