PYTHON
Efficiently Insert into a Sorted List with Python's `bisect`
Learn to use the `bisect` module to maintain a list in sorted order while efficiently inserting new elements, avoiding full list sorts.
import bisect
# A list that needs to be kept sorted
my_sorted_list = [10, 20, 30, 40, 50]
print(f"Original sorted list: {my_sorted_list}")
# Find insertion point for 35
insert_point_35 = bisect.bisect_left(my_sorted_list, 35)
print(f"Insertion point for 35: {insert_point_35}") # Expected: 3
# Insert 35 at the found point
my_sorted_list.insert(insert_point_35, 35)
print(f"List after inserting 35: {my_sorted_list}") # Expected: [10, 20, 30, 35, 40, 50]
# Another insertion using bisect_right (for duplicates, it inserts after existing ones)
insert_point_20 = bisect.bisect_right(my_sorted_list, 20)
print(f"Insertion point for 20 (right): {insert_point_20}") # Expected: 2 (after the existing 20)
# Insert 20
my_sorted_list.insert(insert_point_20, 20)
print(f"List after inserting 20: {my_sorted_list}") # Expected: [10, 20, 20, 30, 35, 40, 50]
# bisect.insort_left is a convenience function that combines bisect_left and list.insert
print(f"List before insort_left: {my_sorted_list}")
bisect.insort_left(my_sorted_list, 25)
print(f"List after insort_left(25): {my_sorted_list}") # Expected: [10, 20, 20, 25, 30, 35, 40, 50]
# bisect.insort_right (or just bisect.insort) combines bisect_right and list.insert
bisect.insort_right(my_sorted_list, 40)
print(f"List after insort_right(40): {my_sorted_list}") # Expected: [10, 20, 20, 25, 30, 35, 40, 40, 50]
How it works: The `bisect` module in Python is designed to maintain a list in sorted order without the overhead of re-sorting the entire list after each insertion. `bisect.bisect_left` (or `bisect_right`) efficiently finds the correct insertion point for a new element using a binary search. The `list.insert()` method then places the element at that precise index. For convenience, `bisect.insort_left` (or `bisect.insort_right`) combines these two steps into a single function call, making it ideal for maintaining sorted data streams or ranked lists with optimal performance.