Merge sorted lists in python

Question

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 = [Obj(1), Obj(3), Obj(8), ...]
b = [Obj(1), Obj(2), Obj(3), ...]
c = [Obj(100), Obj(300), Obj(800), ...]

result = magic(a, b, c)
assert result == [Obj(1), Obj(1), Obj(2), Obj(3), Obj(3), Obj(8), ...]

what does magic look like? My current implementation is

def magic(*args) :
    r = []
    for a in args : r += a
    return sorted(r, cmp)

but that is quite inefficient. Better answers?

Answer 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.