|
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.
|
|