all Python 3bisectfunction

bisect.insort_left()

insertion

Insert x into a sorted list before any equal entries, keeping it sorted; the search is O(log n) but the insertion itself is O(n) due to shifting.

Syntax

bisect.insort_left(a, x)

Each insertion is linear, so building an n-element list by repeated insort_left costs O(n^2) — collecting everything and calling sort() once is far cheaper. The choice between left and right matters only when items that compare equal are still distinguishable objects: left puts the newcomer ahead of them, breaking arrival order, while right appends after.

Examples

import bisect
a = [1, 3, 4, 5]
bisect.insort_left(a, 3)
a # → [1, 3, 3, 4, 5]

See also

Open in the full glossarydocs.python.orgReport an inaccuracy