bisect vs Linear vs set: Lookup Lab

Intro — what this post promises

Need a sorted collection with inserts and membership checks? This lab compares bisect.insort + bisect_left, a linear sorted insert, and a set (fast, but order-free) on Linux localhost — pure lookup, pure insert, and a 70/30 lookup/insert mix.

Related links:

• sorted vs heapq vs bisect localhost lab
• nlargest vs sorted slice localhost lab
• frozenset vs set membership localhost lab
• set vs list membership localhost lab
• itertools chain vs flatten localhost lab
• Counter vs dict tally localhost lab
• array vs list ints localhost lab
• perf_counter vs time localhost lab

Lab honesty (1 Oct 2026 IST): Python 3.13.5. bisect on a list is O(log n) search but O(n) insert (element shift). Affiliates: 0. Complements the sorted/heapq/bisect overview with mixed workloads.

Verdict up front: lookup n=1 000 — set ~26M/s, bisect ~4.5M, linear ~0.24M (set ~5.8× bisect; bisect ~19× linear). Mixed s=2 000: set ~5.1× bisect; bisect ~181× linear-sorted insert.

Arms

Lab topology

lookup: 50k probes on sizes 100/1k/10k
insert: grow to N=1k/5k/10k
mixed: seed S, 70% lookup / 30% insert

Script: lab-evidence/68-bisect-vs-linear-lookup/results/run_lab.py.

Lead table — lookup (p50)

Insert build-to-N (p50)

Batch load? sort once ~3.5× repeated insort. Online sorted inserts pay the shift.

Mixed 70/30 (seed 2 000, 10 k steps)

Reading it

• Need order + online inserts — bisect beats hand linear-sorted insert by ~181× on the mix; still loses to set on raw speed.
• Need membership only — set / frozenset (~6× bisect at n=1 k).
• Batch then query sorted — append + one sort, not N× insort (~3.5×).
• insort is not free — logarithmic find + linear memmove.

Why list+bisect still exists

When you must binary-search a sequence, emit sorted output, or interop with APIs that want a list, bisect is the stdlib tool. For hot membership alone, paying O(n) shifts is the wrong tax — use a set (or a tree/skiplist if you need both order and faster inserts than a list).

Pitfalls

1. Using bisect for membership-only maps — set wins.
2. insorting a bulk load — sort once.
3. Forgetting insert is O(n) — large n + many inserts → consider other structures.
4. Assuming set preserves order — it does not (use sorted list / SortedDict recipes).

When to pick what

Reproduce

python3 lab-evidence/68-bisect-vs-linear-lookup/results/run_lab.py

Evidence: /workspace/lab-evidence/68-bisect-vs-linear-lookup/results/.

Closing

Order costs. On this box set led bisect by ~5.8× on lookup and ~5.1× on a mixed workload, while bisect crushed linear-sorted insert by ~181×. Pick set for speed, bisect when sorted order is a product requirement.