Does python have a sorted list?

The standard Python list is not sorted in any form. The standard heapq module can be used to append in O(log n) to an existing list and remove the smallest one in O(log n), but isn't a sorted list in your definition.

There are various implementations of balanced trees for Python that meet your requirements, e.g. rbtree, RBTree, or pyavl.

Is there a particular reason for your big-O requirements? Or do you just want it to be fast? The sortedcontainers module is pure-Python and fast (as in fast-as-C implementations like blist and rbtree).

The performance comparison shows it benchmarks faster or on par with blist's sorted list type. Note also that rbtree, RBTree, and PyAVL provide sorted dict and set types but don't have a sorted list type.

If performance is a requirement, always remember to benchmark. A module that substantiates the claim of being fast with Big-O notation should be suspect until it also shows benchmark comparisons.

Disclaimer: I am the author of the Python sortedcontainers module.

---

Installation:

pip install sortedcontainers

Usage:

>>> from sortedcontainers import SortedList
>>> l = SortedList()
>>> l.update([0, 4, 1, 3, 2])
>>> l.index(3)
3
>>> l.add(5)
>>> l[-1]
5