an adaptive, stable, natural mergesort

Current version: 2.3, 30 Jul 2003

Status update Dec 2005:

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.

Quick links:


        python-stablesort -- an adaptive, stable, natural mergesort

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 for full details.

- List objects' sort() method now accepts None as the comparison function.
  Passing None is semantically identical to calling sort() with no

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


The module stablesort exports the following three functions:

stablesort.sort(list, cmpfunc=None)
    - sort a list using the new algorithm

    - globally install the new sort algorithm for _all_ list objects,
      i.e. the internal implementation of list.sort() will get replaced
    - restore the original sort method


[1] NEWS:

[2] listsort.txt:

[3] listobject.c:


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.

Valid XHTML 1.0!
This project is not sponsored, endorsed or approved by the PSF.
Last modified Thu Aug 09 17:57:03 UTC 2007.