[Python-ideas] Sorted lists

Terry Reedy tjreedy at udel.edu
Mon Apr 8 00:17:13 EDT 2019

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

More information about the Python-ideas mailing list