heapq.merge in Python: why the full-list benchmark loses to sorted()

Problem. Combining several already sorted streams into one ordered result is the pattern documented for merging timestamped log entries.^[1] A simple baseline concatenates every value and sorts the combined iterable. Baseline. sorted() returns a new sorted list.^[2] Python’s sorting guide also says that Timsort can take advantage of ordering already present in a dataset.^[4] This article measures that full-list baseline against a streaming merge; it does not infer timing from an asymptotic slogan. Solution. heapq.merge(*streams) assumes sorted inputs, returns an iterator and does not pull all data into memory at once.^[1] In the tested path, it keeps the current candidate from each active stream in a heap. Measured result. On this Raspberry Pi, with eight streams and complete list materialisation, heapq.merge was slower in every tested case: 109.450 ms versus 46.618 ms at 128,000 values, a 2.35x slowdown.

Reproduce the result

Complete code

from __future__ import annotations
import heapq
import json
import platform
import random
import statistics
import sys
import timeit
from itertools import chain
K = 8
SEED = 20261002
REPEAT = 7
def make_streams(items_per_stream: int) -> list[list[int]]:
    streams = []
    for stream_index in range(K):
        rng = random.Random(SEED + items_per_stream + stream_index)
        stream = sorted(rng.randrange(1_000_000_000) for _ in range(items_per_stream))
        streams.append(stream)
    return streams
def resort_all(streams: list[list[int]]) -> list[int]:
    return sorted(chain.from_iterable(streams))
def merge_sorted(streams: list[list[int]]) -> list[int]:
    return list(heapq.merge(*streams))
def median_seconds(timer: timeit.Timer, repeat: int = REPEAT) -> tuple[float, list[float]]:
    samples = timer.repeat(repeat=repeat, number=1)
    return statistics.median(samples), samples
def main() -> None:
    sizes = [250, 1_000, 4_000, 16_000]
    cases = []
    for items_per_stream in sizes:
        streams = make_streams(items_per_stream)
        expected = resort_all(streams)
        merged = merge_sorted(streams)
        assert merged == expected
        resort_timer = timeit.Timer(lambda: resort_all(streams))
        merge_timer = timeit.Timer(lambda: merge_sorted(streams))
        resort_median, resort_samples = median_seconds(resort_timer)
        merge_median, merge_samples = median_seconds(merge_timer)
        cases.append(
            {
                "streams": K,
                "items_per_stream": items_per_stream,
                "total_items": len(expected),
                "resort_median_ms": round(resort_median * 1000, 6),
                "heapq_merge_median_ms": round(merge_median * 1000, 6),
                "heapq_merge_ratio": round(merge_median / resort_median, 3),
                "resort_samples_ms": [round(value * 1000, 6) for value in resort_samples],
                "heapq_merge_samples_ms": [round(value * 1000, 6) for value in merge_samples],
            }
        )
    output = {
        "python": sys.version.split()[0],
        "implementation": platform.python_implementation(),
        "platform": platform.platform(),
        "machine": platform.machine(),
        "seed": SEED,
        "streams": K,
        "repeat": REPEAT,
        "correctness": "all heapq.merge outputs matched sorted(chain.from_iterable(streams))",
        "cases": cases,
    }
    print(json.dumps(output, indent=2))
if __name__ == "__main__":
    main()

Command

python3 merge_benchmark.py

Output

$ python3 merge_benchmark.py
{
  "python": "3.13.5",
  "implementation": "CPython",
  "platform": "Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41",
  "machine": "aarch64",
  "seed": 20261002,
  "streams": 8,
  "repeat": 7,
  "correctness": "all heapq.merge outputs matched sorted(chain.from_iterable(streams))",
  "cases": [
    {
      "streams": 8,
      "items_per_stream": 250,
      "total_items": 2000,
      "resort_median_ms": 0.188665,
      "heapq_merge_median_ms": 1.290213,
      "heapq_merge_ratio": 6.839,
      "resort_samples_ms": [
        0.282294,
        0.197424,
        0.188406,
        0.19261,
        0.188665,
        0.188258,
        0.187684
      ],
      "heapq_merge_samples_ms": [
        1.302064,
        1.283342,
        1.318749,
        1.290213,
        1.27049,
        1.296971,
        1.263027
      ]
    },
    {
      "streams": 8,
      "items_per_stream": 1000,
      "total_items": 8000,
      "resort_median_ms": 0.824142,
      "heapq_merge_median_ms": 5.342793,
      "heapq_merge_ratio": 6.483,
      "resort_samples_ms": [
        1.08901,
        0.836512,
        0.810568,
        0.88979,
        0.824142,
        0.803197,
        0.801513
      ],
      "heapq_merge_samples_ms": [
        5.301515,
        5.245201,
        5.18959,
        5.342793,
        5.652309,
        5.639864,
        5.59842
      ]
    },
    {
      "streams": 8,
      "items_per_stream": 4000,
      "total_items": 32000,
      "resort_median_ms": 7.932162,
      "heapq_merge_median_ms": 23.779245,
      "heapq_merge_ratio": 2.998,
      "resort_samples_ms": [
        8.539342,
        8.153567,
        7.513128,
        7.470943,
        8.124327,
        7.804737,
        7.932162
      ],
      "heapq_merge_samples_ms": [
        23.779245,
        23.428748,
        23.377266,
        23.68719,
        23.88554,
        23.902558,
        23.797837
      ]
    },
    {
      "streams": 8,
      "items_per_stream": 16000,
      "total_items": 128000,
      "resort_median_ms": 46.617701,
      "heapq_merge_median_ms": 109.449778,
      "heapq_merge_ratio": 2.348,
      "resort_samples_ms": [
        49.117385,
        48.143486,
        46.278721,
        46.617701,
        47.410584,
        45.471801,
        45.743819
      ],
      "heapq_merge_samples_ms": [
        102.339869,
        105.872397,
        111.845204,
        109.449778,
        110.193013,
        111.25443,
        107.251535
      ]
    }
  ]
}
exit=0

Environment

The run used CPython 3.13.5 on Linux-6.12.47+rpt-pi-v8-aarch64-with-glibc2.41, machine aarch64. It used only the Python standard library. The source file, command, captured stdout, stderr and exit status are retained with the benchmark artefacts.

Methodology

The script builds eight sorted integer streams with seed 20261002. Each case uses 250, 1,000, 4,000 or 16,000 items per stream, giving totals of 2,000, 8,000, 32,000 and 128,000 values. It first compares the complete outputs element by element. It then times sorted(chain.from_iterable(streams)) and list(heapq.merge(*streams)) in seven separate samples with timeit.Timer.repeat; stream construction is outside the timed call.^[3]

There is no explicit warm-up call. The reported value is the median of the seven samples, a declared summary choice that limits the effect of one unusually slow sample; all seven samples for both functions remain in the captured JSON output. The timeit setup is not part of the timed call, and timeit temporarily disables garbage collection by default.^[3]

Limits of the experiment

This is one host, one CPython build, one stream count and one seeded integer workload. Both functions build a complete list, so the run does not measure the memory benefit of consuming heapq.merge lazily. It also does not test disk-backed iterators, an early-stop consumer, unequal stream lengths, custom key functions or other Python implementations. The timings show this workload’s behaviour, not a universal ranking.

Why the documented solution loses this run

heapq.merge is designed for a different contract from a full sort. The documentation describes it as a merge of multiple sorted inputs that returns an iterator, similar to sorted(itertools.chain(*iterables)) but without pulling all input into memory at once.^[1] That distinction matters only if the consumer can use the iterator incrementally. The benchmark calls list(...), which deliberately removes the lazy-output advantage.

The comparison also uses only eight streams. The heap must choose the smallest current item repeatedly, while the baseline hands one combined iterable to CPython’s sorting implementation. The result is visible in the measured timings: heapq.merge takes 6.84 times as long at 2,000 values, 6.48 times as long at 8,000, 3.00 times as long at 32,000 and 2.35 times as long at 128,000.

That does not make the merge function wrong. It answers a narrower question. If the consumer needs every value in a list, and the number of sorted inputs is small, a concatenate-and-sort baseline may win on this runtime. If the consumer can stop early or process records as they arrive, the iterator returned by heapq.merge avoids constructing the complete result list in the same way. That is a change in memory and consumption behaviour, not a speed result measured here.

The implementation boundary

The benchmark keeps the input streams alive for both timed functions and excludes their construction. The baseline creates a combined iterator, sorts its values and returns a list. The merge path maintains a heap of the current head from each stream and advances one input whenever its head is emitted. Equal values are allowed, and the exact output comparison includes duplicates.

These descriptions explain the two tested Python call paths. They do not by themselves predict wall-clock time: Python function calls, list allocation, integer comparison and the implementation of list.sort all contribute to the measured result.

What to choose

Use heapq.merge when the inputs are already sorted and the consumer benefits from an iterator. It is also the direct expression of a k-way merge, which makes the data flow clear. Use concatenation followed by sorted when the final contract is a complete list and a benchmark on the real workload supports it.

The reproducible result here is deliberately less tidy than a specialised-function assumption: the documented k-way merge used more wall-clock time in every full-materialisation case tested. The choice depends on whether the program needs a stream or a list, and on the input count and runtime that actually matter.

Sources

[1] heapq — Heap queue algorithm — Python 3.14.8 documentation

[2] Built-in Functions — Python 3.14.8 documentation

[3] timeit — Measure execution time of small code snippets — Python 3.14.8 documentation

[4] Sorting Techniques — Python 3.14.8 documentation