Bisect algorithm maintains a list in sorted order without having to call sort each time an item is added to the list. bisect module in Python defines a number of functions to keep the array in a sorted fashion. The module uses bisection algorithm to do its work. It inserts the element at the correct position without having to sort the array again every time.

## Important API

Functions provided in bisect module are

• bisect_left(aList, val, lo=0, hi=len(aList)) : Used to find leftmost insertion point for val in aList to maintain sorted order. lo and hi are optional parameters, used to specify a subset of the list which should be considered. If val is already present in aList, the insertion point will be to the left of any existing entries.
• bisect_right(aList, val, lo=0, hi=len(aList)) : Used to find rightmost insertion point for val in aList to maintain sorted order. lo and hi are optional parameters, used to specify a subset of the list which should be considered. If val is already present in aList, the insertion point will be to the right of any existing entries.
• bisect(aList, val, lo=0, hi=len(aList)) : It is similar to bisect_left(), but returns an insertion point which comes to the right of any existing entries of val in aList.
• insort_left(aList, val, lo=0, hi=len(aList)) : Insert val in aList in sorted order. It is equivalent to invoking the bisect_left() function followed by the aList.insert() method.
• insort_right(aList, val, lo=0, hi=len(aList)) : Insert val in aList in sorted order. It is equivalent to invoking the bisect_right() function followed by the aList.insert() method.
• insort(aList, val, lo=0, hi=len(aList)) : Similar to insort_left(), but val is inserted in aList after any existing entries of val.

## Example

Below example shows the use if various functions available in bisect module.

# Program showing application of bisection functions to maintain a list in sorted order
import bisect

# Indexs  0  1   2   3   4   5   6   7  8   9   10  11  12
values = [5, 7, 13, 20, 25, 25, 25, 31, 31, 31, 36, 43, 47]

# 1. Use of bisect, bisect_left and bisect_right routines
print(bisect.bisect(values, 25))
print(bisect.bisect_left(values, 25))
print(bisect.bisect_right(values, 31))

# Output
# 7
# 4
# 10

# 2. Use of insort_right
bisect.insort_right(values, 33)
print(values)

# Output, inserted after rightmost 31
# [5, 7, 13, 20, 25, 25, 25, 31, 31, 31, 33, 36, 43, 47]

# 2. Use of insort_left
bisect.insort_left(values, 23)
print(values)

# Output, inserted after rightmost 20
# [5, 7, 13, 20, 23, 25, 25, 25, 31, 31, 31, 33, 36, 43, 47]

If you start from an empty list and repeatedly use insort to insert the objects into a list, the final list will be sorted.

import bisect

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

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

print(result)

# Output
# [3, 4, 5, 6, 7, 8, 9]