[Python-Dev] sorted()

François Pinard pinard@iro.umontreal.ca
Wed, 25 Sep 2002 17:07:13 -0400

Hi, Guido, and people.

It recurrently happens that newcomers on the Python mailing list are surprised
that list.sort() does not return the sorted list as value.  I quite understand
and agree that this is a good thing, because sorting is done in place, and
Python programmers should stay aware and alert of this fact.

Yet, I often see myself writing things like:

    keys = messages.keys()
    for key in keys:

This is not difficult to write, only slightly annoying.  Writing:

    def sorted(list):
        list = list[:]
        return list

with the goal of simplifying the first excerpt into:

    for key in sorted(message.keys()):

it is not really worth for small programs.  But in larger programs, where one
often loops over the sorted element of a list, it might become reasonable to
write this extra definition.  My feeling is that the idiom is common enough to
be worth a list method, so the above could be written instead:

    for key in message.keys().sorted():

I immediately see an advantage and an inconvenient.  The inconvenient is that
users might confuse `.sort()' with `.sorted()', however we decide to spell
`sorted', so the existence of both may be some kind of trap.  The advantage is
that the `.sorted()' method fits well within how Python has evolved recently,
offering more concise and legible writings for frequent idioms.

Tim invested a lot of courageous efforts so Python `sort' becomes speedier.  A
`.sorted()' method requires separate space to hold the result, using the same
size as the original, and that guaranteed extra-space may eventually be put to
good use for speeding up the sorting even more.  The constraint of a sort
being in-place has indeed a cost, and deep down, we agree that this constraint
is artificial in contexts where `.sorted()' is really what the user needs.

François Pinard   http://www.iro.umontreal.ca/~pinard