heapq.merge vs sorted(chain): Localhost Lab

Intro — what this post promises

Merge k pre-sorted lists via heapq.merge vs sorted(itertools.chain(...)) into a full list (plus consume-only arms). This lab reports records/s on Linux localhost.

It is not sorted-vs-heapq-bisect push/pop (lab 46) and not nlargest (lab 66). This is multi-way merge of sorted inputs.

Related links:

• sorted vs heapq vs bisect localhost lab
• nlargest vs sorted slice localhost lab
• itertools chain vs flatten localhost lab
• zlib vs gzip compress localhost lab
• difflib vs set ops localhost lab
• configparser vs json localhost lab
• html escape vs manual localhost lab
• groupby vs manual localhost lab

Lab honesty (1 Oct 2026 IST): Python 3.13.5. Affiliates: 0. No Docker. Inputs already sorted lists in RAM.

Verdict up front (k=4 × 25 000 = 100 k records): sorted(chain) ~85.15 Mrec/s; heapq.merge→list ~9.82; consume-only merge ~8.54. When everything fits in memory and you need a list, sorted(chain) wins here; use merge for lazy streaming / low peak memory.

Arms

Lab topology

configs: k4×25k · k8×25k · k16×10k · k4×100k · 7 rounds · p50
metric: records/s = total / p50_s

Script: lab-evidence/108-heapq-merge-vs-sorted/results/run_lab.py.

Lead table — k=4 × 25 k (p50 Mrec/s)

Timsort on already-structured int runs is extremely fast; merge pays heap maintenance per output.

Scale sketch (merge→list vs sorted(chain))

When merge still wins the design

• Inputs are lazy iterators you must not fully materialize.
• You only need the first N merged records (islice(merge(...), N)).
• Peak RAM matters more than CPU on huge runs.

If runs are already concrete lists and you need the whole output list, sorted(chain) was faster on this box.

Memory shape

sorted(chain) builds one big list (plus sort scratch). heapq.merge keeps k heads and yields — peak memory tracks the consumers, not a second full copy of every run. On this lab both inputs and outputs fit comfortably; production scale flips the choice.

Reading it

• Full in-memory materialize → prefer sorted(chain) here.
• Streaming / early-stop → prefer heapq.merge.
• Do not confuse with heapq for top-k (lab 66) or bisect insert (lab 46).
• Chain-without-sort is not a correct merge — baseline only.

Early-stop pattern

list(islice(heapq.merge(*runs), 1000)) keeps merge’s O(k) head state and stops after 1000 yields. sorted(chain(...))[:1000] still sorts everything first. If dashboards only need the leading merged page, that early-stop gap dominates any per-record microbench on full materialization.

Integer-run caveat

Our fixtures partition a contiguous integer range — Timsort loves that structure. Random comparable objects or reverse-ish runs can narrow the sorted(chain) lead. Re-measure with your key types before freezing a service default.

Pitfalls

• Calling merge on unsorted inputs (silent wrong order).
• Building list(merge(...)) then wondering why it is slower than sorted.
• Forgetting early-stop with islice when merge’s laziness is the point.
• Comparing to nlargest / single-heap patterns.

Reproduce

python3 lab-evidence/108-heapq-merge-vs-sorted/results/run_lab.py

Evidence: summary.json, summary.txt.

Limits

One Linux box. Integer runs that partition a range (very sort-friendly). Not external-memory k-way merge.

Takeaway

At k=4 × 25 k, sorted(chain) ~85.15 Mrec/s beat heapq.merge→list ~9.82 Mrec/s. Use merge for lazy multi-way streams; use sorted(chain) when all runs are already in RAM and you need a full list.