How to Use bisect.insort in Python to Maintain a Sorted List
Insert items into an already sorted list using Python's bisect.insort to keep it sorted efficiently in O(n) time.
Python code
21 linesimport bisect
def maintain_sorted_list():
data = [3, 1, 4, 1, 5, 9, 2, 6]
sorted_list = []
for num in data:
bisect.insort(sorted_list, num)
print("Original data:", data)
print("Sorted list maintained with insort:", sorted_list)
# Insert new values to maintain sorted order
bisect.insort(sorted_list, 7)
bisect.insort(sorted_list, 0)
bisect.insort(sorted_list, 5)
print("After inserting 7, 0, and 5:", sorted_list)
if __name__ == "__main__":
maintain_sorted_list()Output
Original data: [3, 1, 4, 1, 5, 9, 2, 6]
Sorted list maintained with insort: [1, 1, 2, 3, 4, 5, 6, 9]
After inserting 7, 0, and 5: [0, 1, 1, 2, 3, 4, 5, 5, 6, 7, 9]How it works
The bisect module implements a binary search to find the correct insertion point for each new value in O(log n) time. bisect.insort (an alias for insort_right) inserts the item at that position while shifting existing elements to the right, resulting in an O(n) insertion due to list shifting. This is ideal when the list is already sorted and you need to insert many elements without re-sorting the entire list each time. The insort function adds duplicates to the right of equal values, preserving the sort order.
Common mistakes
- Using `bisect.insort` on an unsorted list, which produces incorrect ordering.
- Forgetting that `insort` modifies the list in place, so it should not be relied upon to return the list.
- Assuming O(1) insertion time; the shift is still O(n) and may be slower than using `bisect` only when the list is huge.
Variations
- Use `bisect.insort_left` to insert duplicates to the left of existing equal values.
- For many insertions, consider using a `heapq` heap, though it doesn't maintain sorted order directly.
Real-world use cases
- Maintaining a leaderboard in sorted order as new scores stream in from many players.
- Keeping a list of events sorted by timestamp while continuously adding new log entries.
- Building a dynamic priority queue where order is based on a numeric key and insertions happen frequently.
Sponsored
More from Concurrency & performance
- Benchmark list.append vs deque.append in Python medium
- Build a Python Performance Profiler That Generates Readable Reports medium
- Graceful Shutdown Executor Context Manager in Python medium
- How to Build a Producer-Consumer Pattern with asyncio.Queue in Python medium
- How to Cancel an asyncio Task with Graceful Cleanup in Python medium
- How to Convert Data in Parallel with ThreadPoolExecutor in Python easy
Keep learning
Related tutorials and quizzes for this topic.