[Python-Dev] add a list.stablesort() method?

Edward Loper edloper at gradient.cis.upenn.edu
Thu Nov 13 04:01:07 EST 2003


Python's list.sort() method has gone through many different 
incarnations, some of which have been stable, and some of which have 
not.  As of Python 2.3, list.sort() *is* stable, but we're told not to 
rely on that behavior. [1]  In particular, it might change for future 
versions/alternate implementations of Python.

Given that, would it make sense to add a list.stablesort() method?  For 
the current implementation of cPython, it would just be another name for 
list.sort().  But adding a new name for it has two advantages:

   1. If we discover a faster sorting algorithm that's not stable,
      then future versions of Python can switch list.sort() to
      use that, but list.stablesort() will still be available for
      anyone who needs a stable sort.

   2. It explicitly marks (to the reader) which sort operations are
      relying on stability.

The main disadvantages that I can think of are:

   1. It adds a new method to the list object, which probably won't get
      used all that often (most tasks don't call for stable sorts).

   2. You can already implement a stablesort procedure in Python (albeit
      less efficiently than the c implementation). [2]

   3. If we do add a non-stable sort in the future, we'll need to
      maintain 2 separate sorting algorithms in listobj.c.

Does this seem like a reasonable addition?

-Edward


[1] <http://www.python.org/doc/current/lib/typesseq-mutable.html>
[2] <http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/52234>





More information about the Python-Dev mailing list