# [Python-Dev] sorted()

**Tim Peters
**
tim.one@comcast.net

*Fri, 27 Sep 2002 14:10:08 -0400*

[Guido]
>* ...
*>* A sorted() method for lists would require a copy. Fran=E7ois argue=
*s
>* that the extra space could be used by the sorting algorithm. But i=
*f
>* 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 spa=
*ce:
>* 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 ma=
*de
>* 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.
*
There's no efficiency argument to be made here unless someone can wri=
te a
sort function this way and demonstrate an improvement.
I expect that would be hard. Back when I wrote the samplesort hybrid=
, I
tried several ways of coding mergesorts too, and they all lost on ran=
dom
data. They all used a temp array of the same size as the original ar=
ray.
The current mergesort does not: it uses a temp array at most half th=
e size.
This effectively doubled the amount of code needed, but cut the size =
of the
working set. I first tried the current mergesort again with a temp a=
rray
the same size as the original, but it again lost (a little on random =
data, a
lot on many kinds of partially ordered data -- for example, take a so=
rted
array, and move its last element to the front; no matter how large th=
e
array, the current mergesort only needs a few dozen temp words to get=
it
sorted again, and caches are much happier with that).