sorted vs heapq vs bisect: Ordered Insert Lab

Intro — what this post promises

Need an ordered collection while values keep arriving? Folklore says “just use bisect.insort” or “use a heap.” This lab times three real patterns on Linux localhost:

1. Batch: append unsorted, then one list.sort / sorted().
2. Online sorted list: bisect.insort into a growing list.
3. Heap: heapq.heappush (and optional push+pop-all to drain).

We report inserts/s (p50) for growing N, plus a stream case: prefill M, then insert k more.

Related links:

• dataclass vs slots vs dict localhost lab
• json vs orjson vs msgpack localhost lab
• python re vs str methods localhost lab
• tempfile NamedTemporaryFile localhost lab
• atomic rename vs overwrite localhost lab
• Why your average latency graph is lying (p50 / p95 / p99)
• fork COW RSS vs spawn localhost lab
• getaddrinfo DNS resolve localhost lab

Lab honesty (1 Oct 2026 IST): Python 3.13.5. Random ints via random.Random(42). Affiliates: 0. Stdlib only — not sortedcontainers / btree.

Verdict up front: at N=5000, append+sort ~7.55M/s and sorted() ~8.89M beat bisect.insort ~2.62M (~0.35×). heapq.push ~17.6M if you only need heap order. At N=20k, insort collapses to ~0.86M (~1168 ns/op). Streaming into a large list: extend+sort often beats repeated insort.

What each tool actually guarantees

bisect looks up the insertion point in O(log n) — then Python’s list insert still slides every trailing element. That memmove is why the curve falls off a cliff as N grows. heapq only bubbles along a heap path; the list is not sorted end-to-end unless you drain it.

Lab topology

Values: random ints, fixed seed
Batch sizes N ∈ {100, 1000, 5000, 20000}
Arms: append+sort | sorted() | bisect.insort | heapq.push | heapq push+pop-all
Stream: prefill M ∈ {1k, 10k, 50k}, then insert k=1000
Metric: p50 wall for full arm ÷ N (or k) → inserts/s

Each arm rebuilds from scratch (or from a fresh prefill copy for stream). Repeats: 5 for N≤5k / small streams, 3 for N=20k and M=50k. Script: lab-evidence/46-sorted-vs-heapq-bisect/results/run_lab.py.

Lead table — N=5000 inserts (p50)

If you need a fully sorted list after a known batch, sort once. If you need online min/max, prefer heapq — do not confuse heap order with a sorted array. The push+pop-all arm is the honest “heap that yields sorted output” baseline (~4.14M here).

Scale — how N hurts bisect

At N=20k, insort is ~1168 ns/op — binary search is cheap; shifting list elements dominates. Timsort on a random batch stays in the ~6–8M/s band. Heap push stays ~17–19M because work per insert grows only logarithmically.

Tiny N (100) makes everyone look “fast enough.” The decision that matters is the curve: does your workload stay at hundreds of inserts, or grow into tens of thousands online?

Stream case — insert k=1000 into a large list

Prefill M, then insert 1000 random values (measure only the insert phase).

At M=50k, extend+sort (~1.73M inserts/s) beats heap (~0.88M) and crushes bisect (~0.20M) for this batch size. Teaching point: online sorted list ≠ cheapest online structure. Buffer and sort when you can; use a heap when you need extract-min without a full sort.

Pitfalls we hit (and you will)

1. Comparing heap push to sorted list. heappush does not leave list fully sorted. Fair “sorted output” arm is push+pop-all.
2. Reporting sum-of-repeats RPS. ops/s here uses p50 batch wall ÷ N.
3. Tiny N. At N=100 everyone looks fast; the story is the curve as N grows.
4. Wrong structure for the API. Need random access by rank → sorted list / bisect. Need peek-min → heap. Need occasional full order → batch sort.
5. insort in a hot ingest loop. Profile first; often a ring buffer + periodic sort wins.

When to pick what

Reproduce

python3 lab-evidence/46-sorted-vs-heapq-bisect/results/run_lab.py
# writes summary.json + summary.txt beside the script

Evidence: /workspace/lab-evidence/46-sorted-vs-heapq-bisect/results/.

Closing

bisect.insort is correct and slow at scale because every insert can move O(n) elements. list.sort amortizes; heapq stays O(log n) if heap order is enough. On this box at N=5k: push ~17.6M, sort batch ~7.6–8.9M, insort ~2.6M; at N=20k insort falls to ~0.86M. Stream into M=50k: extend+sort ~1.73M > heap ~0.88M > bisect ~0.20M. Measure your N — folklore “always insort” does not survive that curve.