[Python-Dev] add a list.stablesort() method?
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.  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). 
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?
More information about the Python-Dev