Insert Element in A Sorted List in Python

Normally, we add elements to the end of a list in python. However, if we are given a sorted list and we are asked to maintain the order of the elements while inserting a new element, it might become a tedious task. In this article, we will discuss different approaches to insert an element in a sorted list in python. 

How to Insert an Element in a Sorted List?

If we are given a sorted list and we are asked to maintain the order of the elements while inserting a new element, we first need to find the position where the new element can be inserted. After that, we can insert the element into the list using slicing or the insert() method. 

Using slicing

To insert a new element in a sorted list using slicing, we will first find the position at which the element will be inserted. For this, we will find the index at which the element in the list is greater than the element to be inserted. After that, we will slice the list into two parts in such a way that one slice contains all the elements smaller than the element to be inserted and another slice contain all the elements greater than or equal to the element to be inserted. 

After creating the slices, we will create a list with the element to be inserted as its only element. Thereafter, we will concatenate the slices. In this way, we can create a sorted list that also contains the new element. You can observe this in the following example.

myList = [1, 2, 3, 5, 6, 7, 8, 9, 10]
print("Original list is:", myList)
element = 4
print("The element to be inserted is:", element)
l = len(myList)
index = 0
for i in range(l):
    if myList[i] > element:
        index = i
        break
myList = myList[:index] + [element] + myList[index:]
print("The updated list is:", myList)

Output:

Original list is: [1, 2, 3, 5, 6, 7, 8, 9, 10]
The element to be inserted is: 4
The updated list is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Using The insert() Method

After finding the index of the element that is greater than the element to be inserted, we can use the insert() method to insert the element in the sorted list. The insert() method, when invoked on a list, takes the index as its first input argument and the element to be inserted as the second input argument. After execution, the element is inserted into the list. 

After finding the element that is greater than the element to be inserted, we will insert the element just before the element using the insert() method as shown below.

myList = [1, 2, 3, 5, 6, 7, 8, 9, 10]
print("Original list is:", myList)
element = 4
print("The element to be inserted is:", element)
l = len(myList)
index = 0
for i in range(l):
    if myList[i] > element:
        index = i
        break
myList.insert(index, element)
print("The updated list is:", myList)

Output:

Original list is: [1, 2, 3, 5, 6, 7, 8, 9, 10]
The element to be inserted is: 4
The updated list is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Suggested Reading: Regression in Machine Learning With Examples

Insert an Element in a Sorted List Using The bisect Module

The bisect module provides us with the insort() function with which we can insert an element to a sorted list. The insort() method takes the sorted list as its first input argument and the element to be inserted as its second input argument. After execution, the element is inserted into the list. You can observe this in the following example.

import bisect

myList = [1, 2, 3, 5, 6, 7, 8, 9, 10]
print("Original list is:", myList)
element = 4
print("The element to be inserted is:", element)
bisect.insort(myList, element)
print("The updated list is:", myList)

Output:

Original list is: [1, 2, 3, 5, 6, 7, 8, 9, 10]
The element to be inserted is: 4
The updated list is: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Conclusion

In this article, we have discussed different approaches to insert elements in a sorted list in python. To know more about lists, you can read this article on list comprehension in python. You might also like this article on dictionary comprehension in python.