[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).
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4