This project is now pretty much obsolete, as shortly after the official Python 2.3 release the sort() method has been changed to guarantee a stable sorting behaviour.
So only users of Python 1.5, 2.1 and 2.2 may find this useful, but even then you really should consider upgrading to at least Python 2.3 for a number of other fixes and improvements.
python-stablesort -- an adaptive, stable, natural mergesort http://py-stablesort.sourceforge.net/ What is python-stablesort ? =========================== python-stablesort is a back-port of the new Python 2.3 stable listsort algorithm to all Python versions (tested with all versions from 1.5.2 to 2.2.3). It can also be regarded as some sort of forward-port in case the default Python list sort() method will change to a non-stable algorithm in the future again. Note that Python's list.sort() has never (and probably will never) guaranteed a stable sorting behaviour. What's so special about the new sort algorithm ? ================================================ In short: + Stable sorting, i.e. entries that compare equal retain their relative order. This is a very important property for many applications that sort data on partial keys. + Typically faster for a wide variety of real-world data. - May require more temporary memory during sorting. More details from the file NEWS [1]: - list.sort() has a new implementation. While cross-platform results may vary, and in data-dependent ways, this is much faster on many kinds of partially ordered lists than the previous implementation, and reported to be just as fast on randomly ordered lists on several major platforms. This sort is also stable (if A==B and A precedes B in the list at the start, A precedes B after the sort too), although the language definition does not guarantee stability. A potential drawback is that list.sort() may require temp space of len(list)*2 bytes (``*4`` on a 64-bit machine). It's therefore possible for list.sort() to raise MemoryError now, even if a comparison function does not. See http://www.python.org/sf/587076 for full details. - List objects' sort() method now accepts None as the comparison function. Passing None is semantically identical to calling sort() with no arguments. - Thanks to Armin Rigo, the last known way to provoke a system crash by cleverly arranging for a comparison function to mutate a list during a list.sort() operation has been fixed. The effect of attempting to mutate a list, or even to inspect its contents or length, while a sort is in progress, is not defined by the language. The C implementation of Python 2.3 attempts to detect mutations, and raise ValueError if one occurs, but there's no guarantee that all mutations will be caught, or that any will be caught across releases or implementations. Also see the file listsort.txt [2] for an in-depth technical discussion. Implementation issues ===================== python-stablesort uses a slightly modified version of the current listobject.c [3] from the Python CVS repository, and adds a wrapper layer in the file stablesort.c. Most things are pretty straightforward - the only tricky part is a small "hack" during module initialization to get access to Python's internal list.sort() method definition. API === The module stablesort exports the following three functions: stablesort.sort(list, cmpfunc=None) - sort a list using the new algorithm stablesort.install() - globally install the new sort algorithm for _all_ list objects, i.e. the internal implementation of list.sort() will get replaced stablesort.uninstall() - restore the original sort method References ========== [1] NEWS: http://python.cvs.sourceforge.net/python/python/dist/src/Misc/NEWS [2] listsort.txt: http://python.cvs.sourceforge.net/python/python/dist/src/Objects/listsort.txt [3] listobject.c: http://python.cvs.sourceforge.net/python/python/dist/src/Objects/listobject.c Copyright ========= python-stablesort is distributed under the same terms as the core Python package - the PSF License Agreement. See the file LICENSE. Wrapper code Copyright (C) 2002-2003 Markus F.X.J. Oberhumer. Actual sort implementation Copyright (C) 2002-2003 the Python Software Foundation. Written by Tim Peters.