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

[Tim Peters]

[Alex Martelli]
>>> try it (and read the Timbot's article included in Python's sources, and the
>>> sources themselves)...

[Kay Schluehr]
>> Just a reading advise. The translated PyPy source
>> pypy/objectspace/listsort.py might be more accessible than the
>> corresponding C code.

[cfbolz]
> indeed. it is at
>
> http://codespeak.net/svn/pypy/dist/pypy/objspace/std/listsort.py

While the Python version is certainly easier to read, I believe Alex
had in mind the detailed English _explanation_ of the algorithm:

    http://cvs.sf.net/viewcvs.py/python/python/dist/src/Objects/listsort.txt

It's a complex algorithm, dripping with subtleties that aren't
apparent from staring at an implementation.

Note that if a list has N elements, sorting it requires at least N-1
comparisons, because that's the minimum number of compares needed
simply to determine whether or not it's already sorted.  A heap-based
priority queue never requires more than O(log(N)) compares to push or
pop an element.  If N is small, it shouldn't make much difference.  As
N gets larger, the advantage of a heap grows without bound.