[Python-Dev] sorted()

[Tim Peters]

[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).