Feature request: sorting a list slice

Raymond Hettinger python at rcn.com
Thu May 18 22:13:56 CEST 2006


George Sakkis wrote:
> It would be useful if list.sort() accepted two more optional
> parameters, start and stop, so that you can sort a slice in place. In
> other words,
>
> x = range(1000000)
> x.sort(start=3, stop=-1)
>
> would be equivalent to
>
> x[3:-1] = sorted(x[3:-1])
>
> but more efficient and without repeating the slice twice. If it's not
> too late for feature additions, I'd love to see this in 2.5.

This is a false optimization.  The slicing steps are O(n) and the sort
step is O(n log n) unless the data has some internal structure that
Timsort can use to get closer to O(n).

If you implemented this and timed in it real apps, I would be surprised
to find that the slice extraction and assignments were the performance
bottleneck.  IMO, a worthwhile performance gain is unlikely.


Raymond




More information about the Python-list mailing list