python bisect.insort(list, value)

Question

does this python module computes an ordered insert into a data structure or it inserts and then sort? been struggling with this kind of thing in python since developing an algorithm in which I have to keep in mind memmory issues thus need a way to insert into a list just in the right position, as it should be done in java using a linkedlist but not sure what to use and how.

Any help will be much appreciated.

Answer 1

This insert value in a list at the correct position, note that it assumes is already sorted. From the documentation:

Insert x in a in sorted order. This is equivalent to a.insert(bisect.bisect_left(a, x, lo, hi), x) assuming that a is already sorted. Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

The last part refers to the fact that insertion on a Python list is O(n). The search is done using binary search.

If you start from an empty list and repeatedly use this algorithm to insert the objects into a list, the final list will be sorted. This algorithm is known as binary insertion sort. For example:

import bisect

l = [1, 3, 7, 5, 6, 4, 9, 8, 2]

result = []
for e in l:
    bisect.insort(result, e)

print(result)

Output

[1, 2, 3, 4, 5, 6, 7, 8, 9]

Note: The complexity of this algorithm is O(n*n) given the O(n) insertion step.