Fri, 27 Sep 2002 14:10:08 -0400
> A sorted() method for lists would require a copy. Fran=E7ois argue=
> that the extra space could be used by the sorting algorithm. But i=
> 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=
> 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=
> 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=
sort function this way and demonstrate an improvement.
I expect that would be hard. Back when I wrote the samplesort hybrid=
tried several ways of coding mergesorts too, and they all lost on ran=
data. They all used a temp array of the same size as the original ar=
The current mergesort does not: it uses a temp array at most half th=
This effectively doubled the amount of code needed, but cut the size =
working set. I first tried the current mergesort again with a temp a=
the same size as the original, but it again lost (a little on random =
lot on many kinds of partially ordered data -- for example, take a so=
array, and move its last element to the front; no matter how large th=
array, the current mergesort only needs a few dozen temp words to get=
sorted again, and caches are much happier with that).