Merging sorted lists/iterators/generators into one stream of values...

[Alex Martelli]

George Sakkis <gsakkis at rutgers.edu> wrote:

> "Lasse Vågsæther Karlsen" <lassevk at gmail.com> wrote:
> 
> > Thanks, that looks like Mike's solution except that it uses the
> > built-in heapq module.
> 
> This make a big difference for the algorithmic complexity; replacing an
> item in a heap is much more efficient than sorting the whole list.

In the most general case, yes.  However, Python's sort ("timsort") is
preternaturally fast when sorting sequences that are mostly sorted
except for maybe one element being in the wrong place... try it (and
read the Timbot's article included in Python's sources, and the sources
themselves)...  I suspect that heapq will still be faster, but by
nowhere as much as one might think.


> Yes, it's a little inconvenient that the builtin heap doesn't take a
> comparison operation but you can easily roll your own heap by transforming
> each item to a (key,item) tuple. Now that I'm thinking about it, it might
> be a good addition to the cookbook.

I believe Python 2.5 adds a key= argument to heapq's functions...


Alex