[Guido]

... A sorted() method for lists would require a copy. François argues that the extra space could be used by the sorting algorithm. But if 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 space: 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 made 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 write 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 random data. They all used a temp array of the same size as the original array. The current mergesort does not: it uses a temp array at most half the 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 array 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 sorted array, and move its last element to the front; no matter how large the array, the current mergesort only needs a few dozen temp words to get it sorted again, and caches are much happier with that).