Insort

Introduction

Insort is a function that combines binary search with in-place sorted insertion. The term “insort” stands for “insert in sorted order.” It is most commonly associated with Python’s built-in bisect module, where insort automates the process of finding the correct insertion point for an element in a sorted list and then placing it there efficiently.

Unlike manual insertions where developers need to first locate an index and then insert, insort handles both steps in one efficient operation.

What Is Insort?

In Python, insort is a function from the bisect module that:

Maintains a list in sorted order.
Performs a binary search to determine the correct insertion index.
Inserts the value without requiring explicit index calculation.

There are two primary versions:

insort_left: Inserts before existing entries (preserving order in case of duplicates).
insort_right: Inserts after existing entries (also preserves order, but places new duplicates later).

Syntax

import bisect

bisect.insort_left(a, x, lo=0, hi=len(a))
bisect.insort_right(a, x, lo=0, hi=len(a))

Parameters:

a: The target sorted list.
x: The element to insert.
lo (optional): Starting index to consider.
hi (optional): Ending index to consider.

Returns:

Nothing; it modifies the list in-place.

Basic Example

import bisect

numbers = [1, 3, 4, 7]
bisect.insort(numbers, 5)
print(numbers)  # Output: [1, 3, 4, 5, 7]

Here, 5 is inserted at the correct position to keep the list sorted.

Left vs Right

Function	Behavior with Duplicates	Example Output (Insert `3`)
`insort_left`	Inserts before duplicates	`[1, 3, 3, 4]`
`insort_right`	Inserts after duplicates	`[1, 3, 3, 4]`

Internally, these use bisect_left() and bisect_right() respectively to determine the insertion point.

Why Use Insort?

Avoids manual binary search + insertion.
Maintains O(log n) search time and O(n) insertion time.
Keeps the list sorted with minimal effort.
Safe and built-in—no need for external libraries.

Under the Hood

Here’s a simplified internal version of insort_left:

def insort_left(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    a.insert(lo, x)

Performance

Operation	Time Complexity
Search Index	O(log n)
Insert Element	O(n) (shift)
Total	O(n)

Binary search ensures fast index finding.
However, the actual list.insert() operation may shift elements and take linear time in the worst case.

Real-World Use Cases

Domain	Use Case
Financial systems	Inserting transactions into ordered timelines
Gaming	Inserting scores into leaderboards
Text processing	Maintaining sorted keyword lists
Machine Learning	Keeping a live sorted list of predictions
Competitive coding	Range queries and online processing

Use Case: Sorted Multiset Simulation

Python doesn’t have a built-in sorted multiset, but insort helps emulate it.

from bisect import insort

class SortedList:
    def __init__(self):
        self.data = []
    
    def add(self, x):
        insort(self.data, x)

    def __repr__(self):
        return str(self.data)

s = SortedList()
s.add(3)
s.add(1)
s.add(2)
print(s)  # Output: [1, 2, 3]

Insort with Custom Data

To use insort with custom objects, separate the key into a secondary list or use a wrapper.

from bisect import insort

people = [('Alice', 30), ('Bob', 25)]
ages = [p[1] for p in people]
new_person = ('Charlie', 27)

i = bisect.bisect_left(ages, new_person[1])
people.insert(i, new_person)
print(people)  # [('Bob', 25), ('Charlie', 27), ('Alice', 30)]

Alternative: SortedContainers Library

The SortedContainers library provides high-performance sorted lists with built-in insertion:

from sortedcontainers import SortedList

sl = SortedList()
sl.add(10)
sl.add(5)
print(sl)  # SortedList([5, 10])

For heavy-duty applications, this library is faster and more flexible than manual insort.

Comparison with Append + Sort

lst = [1, 3, 5]
lst.append(4)
lst.sort()

This works but is inefficient for large lists and repeated operations.

Strategy	Time Complexity
`append + sort()`	O(n log n)
`insort()`	O(n)

For frequent sorted insertions, insort() is superior.

Edge Cases

Empty list: Works fine—insort([], x) inserts x at index 0.
Duplicates: Use insort_left or insort_right to control behavior.
Reverse order: If you need descending order, insort won’t work directly. Consider inserting -x or reversing the list afterward.

Common Patterns

Binary Search with Dynamic Insert

from bisect import bisect_left, insort_left

def insert_and_search(sorted_list, value):
    index = bisect_left(sorted_list, value)
    if index == len(sorted_list) or sorted_list[index] != value:
        insort_left(sorted_list, value)

Maintain Sliding Window

from bisect import insort, bisect_left

window = []

def add_to_window(value, size):
    insort(window, value)
    if len(window) > size:
        del window[bisect_left(window, window[-1])]

Alternatives in Other Languages

Language	Equivalent Concept
C++	`std::lower_bound` + `insert()` on vector
Java	`Collections.binarySearch()` + `add()`
Go	Manual binary search + slice operations
JavaScript	No built-in; requires custom implementation

Summary

Insort is a simple yet powerful tool that merges binary search and sorted insertion into a single, efficient operation. It helps maintain the order of dynamic lists with minimal overhead.