Python: insert into list faster than O(N)?

Question

I have a sorted list L and I have a binary search for determining where in the list to insert an element such that the resulting list will still be in order.

However L.insert(index,object) needs O(N) time complexity.

Is there another data structure for L that will serve the same purpose, but allows for a faster insertion?

Answer 1

Check out the blist module.

https://pypi.python.org/pypi/blist/

It claims O(log n) insertion.

usage:

x = #list contents
y = blist(x)
y.insert(index, object) #now works in O(log n)

Answer 2

A shout out to sortedcontainers.SortedList. This will keep your list in order automatically, with a fast insert time.

from sortedcontainers import SortedList

mylist = SortedList([1, 2, 4, 5])
mylist.add(3)
mylist
#>>> SortedList([1, 2, 3, 4, 5], load=1000)

SortedList insertions are amortized O(sqrt n), or O(cbrt n) with different choices of parameters, but it scales better than blist, which is O(log n), because the constants are much better. There is a very in-depth look at performance on their website.

Alternatively, you might be wanting a priority queue in which case you can get potentially-faster inserts with the heapq module.