[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. -- http://mail.python.org/mailman/listinfo/python-list
