[Python-ideas] Sorted lists

[Terry Reedy]

On 4/7/2019 10:32 PM, Steven D'Aprano 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:

Does the CPython C-coded list structure have a unused bit that could be 
used for this?  (I realized that other implementations might have a 
different answer.)  Dunder names are not intended for directly use in 
code.  If __issorted__ is a property, it could instead by .is_sorted or 
a new .is_sorted method, where is_sorted(bool) sets the property.

-- 
Terry Jan Reedy