heapq.merge() Silently Returns Wrong Results on Unsorted Input (tested)

heapq.merge() looks like a drop-in replacement for sorted(itertools.chain(*iterables)) that's faster because it does a streaming k-way merge instead of a full sort. That speed comes from a hidden assumption: each input iterable must already be sorted. We measured what happens when that assumption is silently violated.

1. One unsorted input is enough to break the output -- with no error

import heapq

a = [1, 5, 2, 8]   # NOT sorted
b = [3, 4, 9]      # sorted

result = list(heapq.merge(a, b))
print(result)
print("is it sorted?", result == sorted(result))

[1, 3, 4, 5, 2, 8, 9]
is it sorted? False

Measured: heapq.merge() ran to completion and returned a list that looks almost sorted -- but isn't. It compares the current front element of each input stream and repeatedly takes the smaller one, which only produces a globally sorted result if each stream was individually non-decreasing to begin with. Here a wasn't, so the 2 buried after the 5 and 8 in a surfaces out of order in the output. There's no exception and no warning -- the bad merge looks exactly like a successful call.

2. sorted(itertools.chain(...)) doesn't have this problem

import heapq, itertools

a = [1, 5, 2, 8]
b = [3, 4, 9]

print("heapq.merge:   ", list(heapq.merge(a, b)))
print("sorted(chain): ", sorted(itertools.chain(a, b)))

heapq.merge:    [1, 3, 4, 5, 2, 8, 9]
sorted(chain):  [1, 2, 3, 4, 5, 8, 9]

Measured: sorted(itertools.chain(a, b)) gives the correct answer regardless of whether a and b were pre-sorted, because it sorts everything from scratch. heapq.merge() only beats that approach when its precondition actually holds -- if there's any doubt about whether an input is sorted, the "faster" function is the one that silently gives the wrong answer.

3. reverse= and key= have the exact same precondition, just rephrased

import heapq

# reverse=True needs each input sorted *descending*
c = [8, 5, 1, 2]   # NOT sorted descending
d = [9, 4, 3]       # sorted descending
print(list(heapq.merge(c, d, reverse=True)))

# key=len needs each input sorted BY that key already
e = ["bb", "a", "ccc"]   # NOT sorted by len
f = ["dddd", "z"]         # sorted by len
print(list(heapq.merge(e, f, key=len)))

[9, 8, 5, 4, 3, 1, 2]
['bb', 'a', 'ccc', 'dddd', 'z']

Measured: both calls complete and return plausible-looking lists that are not actually sorted (by the relevant order). reverse=True doesn't sort descending for you -- it still just assumes each input stream is already arranged that way. key=len doesn't sort each input by length first either -- it assumes that's already true. In both cases we checked: no exception, no warning, just a wrong result that passes a casual glance.

Frequently asked questions

Does heapq.merge() sort its inputs for you?

No -- we measured it assuming every input iterable is already individually sorted (or sorted descending with reverse=True, or sorted by the key= function). It does a streaming merge, not a sort, and never checks the precondition.

What happens if you call heapq.merge() on an unsorted list?

It runs without error and returns a list that looks plausible but isn't actually sorted -- we measured a concrete case where [1, 5, 2, 8] merged with a sorted [3, 4, 9] produced [1, 3, 4, 5, 2, 8, 9], which is not in order.

Does heapq.merge() raise a warning if an input isn't sorted?

No -- we measured zero warnings and no exception using Python's warnings module in catch-all mode around a call with deliberately unsorted input.

Is heapq.merge() always correct to use instead of sorted(itertools.chain(...))?

Only when you're certain every input is already sorted (and, if used, sorted consistently with any key= or reverse= you pass). We measured sorted(itertools.chain(*iterables)) giving the correct result regardless of input order, while heapq.merge() gave a silently wrong one on the same unsorted input.

Written with AI assistance. Measured on 2026-10-04 with Python 3.13.5's built-in heapq module: called merge() on inputs that weren't individually sorted, with and without key= and reverse=, and checked for any exception or warning. PlainHeaders is our extension; Python's heapq module is built in.