[Python-ideas] Sorted lists

[Cameron Simpson]

On 08Apr2019 12:32, Steven D'Aprano <steve at pearwood.info> wrote:
>There are quite a few important algorithms which require lists to be
>sorted. For example, the bisect module, and for statistics median and
>other quantiles.
>
>Sorting a list is potentially expensive: while Timsort is very
>efficient, it is still ultimately an O(N log N) algorithm which limits
>how efficient it can be. Checking whether a list is sorted is O(N).
>
>What if we could check that lists were sorted in constant time?
>
>Proposal: let's give lists a dunder flag, __issorted__, that tracks
>whether the list is definitely sorted or not:
[...specifics, all looking pretty sane for a hand maintained advisory 
flag...]
>- insert(), append(), extend(), __setitem__() will be a tiny bit
>  slower due to the need to set the flag.

__setitem__ concerns me, along with other modification methods: what 
about subclasses(*)? Every existing subclass which overrides __setitem__ 
now needs to grow code to maintain __issorted__ if they do not 
themselves call list.__setitem__.

Also, should this imply an issorted() builtin to consult an instance's 
__issorted__ dunder flag? Should such a builtin return False for 
instances without an __issorted__ flag? I'm thinking yes since the flag 
is intended to mean known-to-be-sorted.

Cheers,
Cameron Simpson <cs at cskk.id.au>

* I _know_ subclassing builtins is discouraged, but it is supported and 
can be done if one is conservative.