Does python have a sorted list?

Question

By which I mean a structure with:

• O(log n) complexity for x.push() operations
• O(log n) complexity to find an element
• O(n) complexity to compute list(x) which will be sorted

I also had a related question about performance of list(...).insert(...) which is now here.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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).

Answer 5

import bisect

class sortedlist(list):
    '''just a list but with an insort (insert into sorted position)'''
    def insort(self, x):
        bisect.insort(self, x)

Answer 6

An AVL Tree coupled with in-order traversal will solve this problem in the required time complexity.

Answer 7

It may not be hard to implement your own sortlist on Python. Below is a proof of concept:

import bisect

class sortlist:
    def __init__(self, list):
        self.list = list
        self.sort()
    def sort(self):
        l = []
        for i in range(len(self.list)):
            bisect.insort(l, self.list[i])
        self.list = l
        self.len = i
    def insert(self, value):
        bisect.insort(self.list, value)
        self.len += 1
    def show(self):
        print self.list
    def search(self,value):
        left = bisect.bisect_left(self.list, value)
        if abs(self.list[min([left,self.len-1])] - value) >= abs(self.list[left-1] - value):
            return self.list[left-1]
        else:
            return self.list[left]

list = [101, 3, 10, 14, 23, 86, 44, 45, 45, 50, 66, 95, 17, 77, 79, 84, 85, 91, 73]
slist = sortlist(list)
slist.show()
slist.insert(99)
slist.show()
print slist.search(100000000)
print slist.search(0)
print slist.search(56.7)

========= Results ============

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 101]

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 99, 101]

101

3

50

Answer 8

Use the standard library bisect module or the third-party sortedcontainers package. Alternately, the heapq module solves the problem by implementing a heap queue.

Answer 9

Interesting case: if your list L is already sorted (for example because you appended them in a sorted order), you can benefit from a fast lookup in O(log n) with a standard Python list with this method:

import bisect
def in_sorted_list(elem, sorted_list):
    i = bisect.bisect_left(sorted_list, elem)
    return i != len(sorted_list) and sorted_list[i] == elem
L = ["aaa", "bcd", "hello", "world", "zzz"]
print(in_sorted_list("hellu", L))       # False

More details in this answer.