[Python-Dev] sorted()

Guido van Rossum guido@python.org
Fri, 27 Sep 2002 11:19:26 -0400

Since François is probably waiting for a pronouncement for me, let me
say that I think this is a problem that should not be addressed by
changes to the language, builtins or library.

A sorted() method for lists would require a copy.  François argues
that the extra space could be used by the sorting algorithm.  But if
the requirement is that the original array must not be shuffled at
all, I expect that there's no way you can make use of the extra space:
you have to make a copy of the whole list first, which then gets
shuffled in various ways.  I suppose it would be possible to write a
sorting algorithm that made some use of the availability of an output
array, but rewriting the sort code once again so that you can avoid
writing a three line function doesn't seem a good trade-off.

More generalized solutions seem overkill: I've not seen demand for
sorting other container types (except for list subclasses).

The argument against making sort() return self (while sorting
in-place) still holds, and this argument also means that having a
sorted() that sorts in-place is a bad idea.

You could consider adding a "sort" option to keys(), values() and
items(), but that doesn't solve other similar cases.

I think you'll just have to live with it.  Or you can create a dict
subclass that sorts its keys.

--Guido van Rossum (home page: http://www.python.org/~guido/)