Does python have a sorted list?

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

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.

Though I have still never checked the "big O" speeds of basic Python list operations, the bisect standard module is probably also worth mentioning in this context:

import bisect
L = [0, 100]

bisect.insort(L, 50)
bisect.insort(L, 20)
bisect.insort(L, 21)

print L
## [0, 20, 21, 50, 100]

i = bisect.bisect(L, 20)
print L[i-1], L[i]
## 20, 21

PS. Ah, sorry, bisect is mentioned in the referenced question. Still, I think it won't be much harm if this information will be here )

PPS. And CPython lists are actually arrays (not, say, skiplists or etc) . Well, I guess they have to be something simple, but as for me, the name is a little bit misleading.

So, if I am not mistaken, the bisect/list speeds would probably be:

• for a push(): O(n) for the worst case ;
• for a search: if we consider the speed of array indexing to be O(1), search should be an O(log(n)) operation ;
• for the list creation: O(n) should be the speed of the list copying, otherwise it's O(1) for the same list )

Upd. Following a discussion in the comments, let me link here these SO questions: How is Python's List Implemented and What is the runtime complexity of python list functions

Though it does not (yet) provide a custom search function, the heapq module may suit your needs. It implements a heap queue using a regular list. You'd have to write your own efficient membership test that makes use of the queue's internal structure (that can be done in O(log n), I'd say...). There is one downside: extracting a sorted list has complexity O(n log n).