Merge Sorted Lists In Python

I have a bunch of sorted lists of objects, and a comparison function class Obj : def __init__(p) : self.points = p def cmp(a, b) : return a.points < b.points a

Solution 1:

Python standard library offers a method for it: heapq.merge.
As the documentation says, it is very similar to using itertools (but with more limitations); if you cannot live with those limitations (or if you do not use Python 2.6) you can do something like this:

sorted(itertools.chain(args), cmp)

However, I think it has the same complexity as your own solution, although using iterators should give some quite good optimization and speed increase.

Solution 2:

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

Solution 3:

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

Solution 4:

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.

Solution 5:

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.