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

Tim Peters tim.peters at
Sat Oct 8 18:24:03 CEST 2005

[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/ might be more accessible than the
>> corresponding C code.

> indeed. it is at

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

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.

More information about the Python-list mailing list