The list is a container data type that represents a collections of ordered elements.

Sometimes we may want to maintain a list in sorted state without having to sort the list manually every time a new item is added. This involves inserting the new element at exactly  the correct position in the list  that will maintain the sorted order of the list. 

The bisect module in the standard library offers tools necessary for maintaining a sorted list. 

The insort() function in the  bisect module inserts a value in the sorted list maintaining the order. 

insort(x, lst, lo = 0, hi = None, key = None)
lst Required. The list in which the element is to be inserted.
x Required. The element to be inserted.
lo The starting index
hi the ending index
key A function to be used as the sorting criteria. 
 import bisect 
a = [1, 2, 4, 5] 

bisect.insort(a, 3) 
print(a)

In the above example:

  • We imported the insort() function from the bisect module
  • We then used the function to insert elements 3 to list a while maintaining the sorted order.

One important thing to note is that the insort() function assumes that the  list is already sorted and will not  sort the list for you. In case the list is not correctly sorted it will simply insert the element at the position where the list would presumably remains sorted.  You should therefore make sure that the list is already sorted in the correct order before using insort() to insert new elements.

from bisect import insort

lst = [('Python', 1), ('Java', -3), ('C++', 5)]

element = ('PHP', -2)

insort(lst, element, key = lambda x: abs(x[1]) )
print(lst)

In the above example, the list elements are tuples and are sorted based on the absolute values of their second element. We passed  to the insort() function a key  in form of a lambda function i.e lambda x: abs(x[1]) so that the element to be inserted will maintain this order.

Conclusion

The insort() function is an optimized insertion algorithm that runs in logarithmic time O(log n). This makes it far more efficient than manually sorting the list each time a new element is inserted in the list.

The function assumes that the input list is already in a sorted state and will not sort the list if otherwise.