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