Merging sorted lists/iterators/generators into one stream of values...
tim.peters at gmail.com
Sat Oct 8 18:24:03 CEST 2005
>>> try it (and read the Timbot's article included in Python's sources, and the
>>> sources themselves)...
>> Just a reading advise. The translated PyPy source
>> pypy/objectspace/listsort.py 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