Bisect Module

Introduction

The Bisect module in Python provides support for maintaining a list in sorted order without having to sort the list after each insertion. It uses binary search under the hood to locate the insertion point efficiently. This is especially useful when you’re building a sorted collection dynamically and want to ensure that every new element is inserted in the correct position in logarithmic time.

This module is part of Python’s standard library, which means you don’t need to install anything — just import and go.

Core Features

The bisect module provides the following main functions:

bisect_left(a, x[, lo[, hi]])
bisect_right(a, x[, lo[, hi]]) (also available as bisect)
insort_left(a, x[, lo[, hi]])
insort_right(a, x[, lo[, hi]]) (also available as insort)

All of these operations assume that the list a is already sorted.

Why Use Bisect?

Efficient insertion into sorted lists
Faster than manually scanning the list
Underlying implementation uses binary search, giving O(log n) performance for search
Ideal for maintaining priority queues, leaderboards, event logs, etc.

`bisect_left`

import bisect

a = [1, 3, 4, 6, 7]
index = bisect.bisect_left(a, 4)  # Returns 2

This function returns the leftmost position in the list where an element should be inserted to maintain sorted order. If the element already exists, the new element will be placed before it.

`bisect_right` or `bisect`

index = bisect.bisect_right(a, 4)  # Returns 3

This function returns the rightmost position where the element can be inserted. If the element already exists, the new one will be placed after it.

`insort_left`

bisect.insort_left(a, 4)
# a becomes: [1, 3, 4, 4, 6, 7]

Inserts the value into the list while maintaining sorted order, placing it before any existing equal elements.

`insort_right` or `insort`

bisect.insort(a, 4)
# a becomes: [1, 3, 4, 4, 6, 7]

This version inserts after any existing equal elements.

Performance

All the bisect and insort operations run in:

O(log n) for the binary search (to find the position)
O(n) for the actual insertion (since Python lists are dynamic arrays)

This means the total cost of insort operations is O(n) due to shifting elements, even though the search part is logarithmic.

Custom Insertion Using Key Functions

The bisect module does not support key functions like sorted() or min(). If you’re working with complex objects (e.g., tuples or custom classes), you’ll need to extract and manage keys manually.

import bisect

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

people = [Person("Alice", 25), Person("Bob", 30), Person("Charlie", 35)]
ages = [p.age for p in people]

new_person = Person("Dave", 32)
index = bisect.bisect_right(ages, new_person.age)
people.insert(index, new_person)

Common Use Cases

Scenario	How Bisect Helps
Inserting into a leaderboard	Maintains scores in sorted order
Priority queue	Keeps tasks ordered without re-sorting
Event timelines	Insert events as they arrive in order
Auto-complete systems	Efficient prefix searching in sorted data
Range counting	Count items falling within a numeric range

Limitations

Works only with already sorted lists
Cannot use custom comparison logic or key functions
Not suitable for large-scale insertions where shifting elements would be too costly

For more powerful needs, consider using:

bisect.bisect_right with collections.deque for faster insertions at either end
blist or third-party sorted list implementations like sortedcontainers

Alternatives and Related Modules

Module/Tool	Use Case
`heapq`	Priority queues (min-heap)
`sortedcontainers`	Drop-in sorted list/dict/set
`deque`	Fast appends/pops from both ends
`array`	Typed arrays for numerical values

Summary

The bisect module in Python offers a clean and efficient way to maintain sorted lists without repeated sorting. Whether you’re managing a scoreboard, keeping logs in order, or inserting time-sensitive events, bisect lets you do it efficiently using binary search under the hood.

Although limited in flexibility, its speed and simplicity make it a valuable tool in many coding situations — especially when used with scalar data and sorted sequences.