generic xmerge ?

[bonono at gmail.com]

million thanks. So the default compare funcion of heapq also do it like
sort ?

The size of the list is not very large but has the potential of being
run many times(web apps). So I believe second one should be faster(from
the app perspective) as it goes into the optimized code quickly without
all the overheads in the merge case.

Alex Martelli wrote:
> You can do it either way -- simplest, and pretty fast, is to concatenate
> them all and sort the result (the sort method is very good at taking
> advantage of any sorting that may already be present in some parts of
> the list it's sorting), but you can also try a merging approach.  E.g.:
>
>
> import heapq
>
> def merge_by_heap(*lists):
>   sources = [[s.next(), i, s.next]
>                     for i, s in enumerate(map(iter,lists))]
>   heapq.heapify(sources)
>   while sources:
>     best_source = sources[0]
>     yield best_source[0]
>     try: best_source[0] = best_source[-1]()
>     except StopIteration: heapq.heappop(sources)
>     else: heapq.heapreplace(sources, best_source)
>
> Now, L=list(merge_by_heap(l1, l2, l3)) should work, just as well as,
> say, L = sorted(l1+l2+l3).  I suspect the second approach may be faster,
> as well as simpler, but it's best to _measure_ (use the timeit.py module
> from the standard library) if this code is highly speed-critical for
> your overall application.
> 
> 
> Alex