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]