Python provides methods for sorting elements of the list. We can keep elements of different types in a list in Python and sort them. Though it does provides a way to sort elements, we need an efficient way to insert elements in the sorted list. The process of adding an element and then sorting the array again each time after adding a new element to the sorted list can be time-consuming. To solve this problem, Python provides us with a module named **bisect** which helps us find a position to insert an element in a sorted array and insert it. The **bisect** module uses a basic bisection algorithm to find the best suitable for inserting elements in an array. We'll explain various methods of this module with a simple example as a part of this tutorial.

As a part of our first example, we'll demonstrate how we can add elements to the sorted array using **bisect_left()** method.

**bisect_left(a, x, lo=0, hi=len(a))**- It accepts array and element that we want to insert into the array as input and returns an index where we can insert an element in the array. It makes sure for us that the array will still be sorted array after the insertion of the new element. This method will return a left-most index in the array if the element we try to insert is already present one or more times in the array.

Below we have created a simple list and inserting element 7 two times into it. We are then inserting element 12 into the list. We are printing the index returned by **bisect_left()** method each time to see which position it returns. We can notice that when we first time tried to insert element 7 into the array, it returned index 6 because 7 is already present in the list and this new 7 should be inserted before that 7. When we tried to insert 7 again, it returns index 6 again which will be inserted before already present two entries of 7. When we try to insert elements greater than all elements of the array it returns an index same as the size of the array.

In [16]:

```
import bisect
lst = [1,2,3,4,5,6,7,8,9,10]
print("List Initially : {}".format(lst))
idx = bisect.bisect_left(lst, 7)
print("Returned Index : {} for Inserting {}".format(idx, 7))
lst.insert(idx, 7)
idx = bisect.bisect_left(lst, 7)
print("Returned Index : {} for Inserting {}".format(idx, 7))
lst.insert(idx, 7)
idx = bisect.bisect_left(lst, 12)
print("Returned Index : {} for Inserting {}".format(idx, 12))
lst.insert(idx, 12)
print("List After Insertion : {}".format(lst))
```

As a part of our second example, we'll demonstrate how we can use the method **bisect_right()** to insert an element into the sorted array.

**bisect_right(a, x, lo=0, hi=len(a))**- This method works exactly like**bisect_left()**with only change that whenever element is already present it returns index which is last after all possible entry of the item we are trying to insert. It returns the right-most index in case of repetition.

Our code for this example is exactly the same as our code for the previous example with the only change that we have used **bisect_right()** method this time instead. We can notice that when we try to insert 7 two times, it returned a different index each time. The first time it returns index 7 which is after the present entry of 7. The second time it returns index 8 which is after both existing 7 entries.

In [18]:

```
import bisect
lst = [1,2,3,4,5,6,7,8,9,10]
idx = bisect.bisect_right(lst, 7)
print("Returned Index : {} for Inserting {}".format(idx, 7))
lst.insert(idx, 7)
idx = bisect.bisect_right(lst, 7)
print("Returned Index : {} for Inserting {}".format(idx, 7))
lst.insert(idx, 7)
idx = bisect.bisect_right(lst, 12)
print("Returned Index : {} for Inserting {}".format(idx, 12))
lst.insert(idx, 12)
print("List After Insertion : {}".format(lst))
```

As a part of our third example, we'll explain how we can use **bisect()** method to insert elements into the sorted array. The **bisect()** method works exactly like **bisect_right()** method.

Our code for this example is also exactly the same as our previous example with the only change that we are using **bisect()** method instead. We can notice that our output is exactly the same as our previous example.

In [17]:

```
import bisect
lst = [1,2,3,4,5,6,7,8,9,10]
idx = bisect.bisect(lst, 7)
print("Returned Index : {} for Inserting {}".format(idx, 7))
lst.insert(idx, 7)
idx = bisect.bisect(lst, 7)
print("Returned Index : {} for Inserting {}".format(idx, 7))
lst.insert(idx, 7)
idx = bisect.bisect(lst, 12)
print("Returned Index : {} for Inserting {}".format(idx, 12))
lst.insert(idx, 12)
print("List After Insertion : {}".format(lst))
```

As a part of our fourth example, we are demonstrating how we can directly insert elements into a sorted array using **insort_left()** method.

**insort_left(a, x, lo=0, hi=len(a))**- This method works exactly like**bisect_left()**with only change that it actually inserts element at index which would have been returned by**bisect_left()**method. It inserts element in place.

Our code for this example is also the same as our previous examples where we are inserting elements into an existing sorted array. We are printing the array after each insertion.

In [25]:

```
import bisect
lst = [1,2,3,4,5,6,7,8,9,10]
print("List Initially : {}".format(lst))
bisect.insort_left(lst, 7)
print("List After 1st Insertion : {}".format(lst))
bisect.insort_left(lst, 7)
print("List After 2nd Insertion : {}".format(lst))
bisect.insort_left(lst, 12)
print("List After 3rd Insertion : {}".format(lst))
```

Our fifth example explains how we can insert elements into a sorted array using **insort_right()** method. The method works exactly like **bisect_right()** method but instead of returning an index to insert an element, it actually inserts an element into that position.

Our code for this example is like our previous example. It gives the same results as our previous examples.

In [26]:

```
import bisect
lst = [1,2,3,4,5,6,7,8,9,10]
print("List Initially : {}".format(lst))
bisect.insort_right(lst, 7)
print("List After 1st Insertion : {}".format(lst))
bisect.insort_right(lst, 7)
print("List After 2nd Insertion : {}".format(lst))
bisect.insort_right(lst, 12)
print("List After 3rd Insertion : {}".format(lst))
```

Our sixth example explains how we can use **insort()** method which is exactly like **bisect()** method but actually inserts items into a sorted array. Our code for this part as well is almost the same as our previous examples.

In [27]:

```
import bisect
lst = [1,2,3,4,5,6,7,8,9,10]
print("List Initially : {}".format(lst))
bisect.insort(lst, 7)
print("List After 1st Insertion : {}".format(lst))
bisect.insort(lst, 7)
print("List After 2nd Insertion : {}".format(lst))
bisect.insort(lst, 12)
print("List After 3rd Insertion : {}".format(lst))
```

As a part of our seventh example, we are using **bisect_left()** and **bisect_right()** methods to determine which elements in the sorted array are less than and greater than the given input element. The code for this part is simple and self-explanatory like our previous examples.

In [55]:

```
import bisect
lst = [1,2,3,4,5,6,7,8,9,10]
print("List Initially : {}".format(lst))
idx1 = bisect.bisect_left(lst, 7)
print("Elements Less Than {} : {}".format(7, lst[:idx1]))
idx2 = bisect.bisect_right(lst, 7)
print("Elements Greater Than {} : {}".format(7, lst[idx2:]))
idx1 = bisect.bisect_left(lst, 10)
print("Elements Less Than {} : {}".format(10, lst[:idx1]))
idx2 = bisect.bisect_right(lst, 10)
print("Elements Greater Than {} : {}".format(10, lst[idx2:]))
idx1 = bisect.bisect_left(lst, 0)
print("Element Less Than {} : {}".format(0, lst[:idx1]))
idx2 = bisect.bisect_right(lst, 0)
print("Element Greater Than {} : {}".format(0, lst[idx2:]))
```

Our eight example demonstrates how we can use methods **bisect_left()** and **bisect_right()** methods to find element smaller and bigger than the element supplied as input. If the element is already present in the array then it does not return that element, instead, it returns an element that is exactly bigger or smaller than it. If an element bigger or smaller is not present then it returns None.

In [7]:

```
import bisect
lst = [1,2,3,4,5,6,7,8,9,10]
print("List Initially : {}".format(lst))
idx1 = bisect.bisect_left(lst, 7)
print("Element Less Than {} : {}".format(7, lst[idx1-1] if idx1 != 0 else None))
idx2 = bisect.bisect_right(lst, 7)
print("Element Greater Than {} : {}".format(7, lst[idx2] if idx2<len(lst) else None))
idx1 = bisect.bisect_left(lst, 10)
print("Element Less Than {} : {}".format(10, lst[idx1-1] if idx1 != 0 else None))
idx2 = bisect.bisect_right(lst, 10)
print("Element Greater Than {} : {}".format(10, lst[idx2] if idx2<len(lst) else None))
idx1 = bisect.bisect_left(lst, 0)
print("Element Less Than {} : {}".format(0, lst[idx1-1] if idx1 != 0 else None))
idx2 = bisect.bisect_right(lst, 0)
print("Element Greater Than {} : {}".format(0, lst[idx2] if idx2<len(lst) else None))
```

This ends our small tutorial explaining how we can use various methods provided by **bisect** module to insert elements efficiently into a sorted array. Please feel free to let us know your views in the comments section.

Sunny Solanki

Simple Guide to Style Display of Pandas DataFrames

Simple Guide to Set Pandas Options to Better Display DataFrames

configparser - Simple Guide to Create and Parse Configuration Files

Simple and Useful Functions of "OS" Module of Python