Does Python save when something has been sorted inside?

Question

For example, if I call

L = [3,4,2,1,5] L = sorted(L) 

I get a sorted list. Now, in the future, if I want to execute some other view on L, does Python automatically know "this list has been sorted before and not changed since then, so we can perform some internal optimizations for how we perform this other view sort ", for example, sort in reverse order, etc.

Answer 1

No, it is not. The sorting algorithm is designed to use (partially) sorted inputs, but the list itself does not "remember" sorting in any case.

(This is actually a detail of the CPython implementation, and future versions / various implementations may cache the fact that the list was just sorted. However, I'm not sure if this can be done without slowing down all the operations that modify the list, for example append .)

Answer 2

As commentators noted, regular Python lists are sorted in order and sorted efficiently (thanks, Timsort!), But don’t remember and do not save the sort status.

If you need lists that invariably maintain their sorted status, you can install the SortedContainers package from PyPI .

 >>> from sortedcontainers import SortedList >>> L = SortedList([3,4,2,1,5]) >>> L SortedList([1, 2, 3, 4, 5]) >>> L.add(3.3) >>> L SortedList([1, 2, 3, 3.3, 4, 5]) 

Note that the regular append method becomes add because the element is not added to the end. He added, where necessary, in sorting order. There is also a SortedListWithKey type that allows you to explicitly specify your key / sort order.

Answer 3

Some of this, at least the specific issue of reverse sorting, can be accomplished with numpy :

 import numpy as np L = np.array([3,4,2,1,5]) a = np.argsort(L) b = L[a] r = L[a[::-1]] print L [3 4 2 1 5] print b [1 2 3 4 5] print r [5, 4, 3, 2, 1] 

That is, here we just do the sorting once (to create a , sort indexes), and then we can manipulate a to do other different kinds, such as normal sort b , and reverse sort r . And many others would be as light as all the other elements.