Bisect

Suppose you want to keep a list sorted in Python. You could repeatedly sort it after adding an item at the end, or you could call insort() from the bisect module.

With insort, an element is inserted in sorted order. The list must be already sorted—internally, the bisect() method is used to determine the insertion point.

Example

Here we use the bisect module in various ways. Generally with bisect, the insort() method is most important—it internally calls bisect on its own.

Step 1 It is important to call insort() on an already-sorted list. An empty list has no values, so it is considered sorted.

Step 2 With bisect_left, we can find the index of an existing element if one exists (otherwise, the insertion point is returned).

Step 3 We call insort() again, and it places the value -1 at the first index in the list.

Step 4 We can specify a key to keep the list sorted upon. We add tuples to the list, and specify (with a lambda) the second item in the tuples.

import bisect

# Step 1: create an empty list and add 3 integers in sorted order.
values = []
bisect.insort(values, 5)
bisect.insort(values, 1)
bisect.insort(values, 10)
print(values)

# Step 2: find the index of the value 4 within the sorted list.
position = bisect.bisect_left(values, 5)
print(position, values[position])

# Step 3: insert another value in sorted order.
bisect.insort(values, -1)
print(values)

# Step 4: create new list of tuples, and keep sorted by the second tuple item.
tuples = []
bisect.insort(tuples, ("bird", 10), key=lambda x: x[1])
bisect.insort(tuples, ("ant", 20), key=lambda x: x[1])
bisect.insort(tuples, ("apple", 0), key=lambda x: x[1])
print(tuples)[1, 5, 10]
1 5
[-1, 1, 5, 10]
[('apple', 0), ('bird', 10), ('ant', 20)]

Summary

With the bisect module, we have useful methods for binary search—we can call bisect to find insertion points for an element to keep a list sorted as we go along.