Skip to content
Python heapq.merge: check that every input is already sorted

Python heapq.merge: check that every input is already sorted

November 20, 2026

heapq.merge is useful when several producers already emit ordered records. Passing an unsorted producer can yield an unsorted result without an exception.

Set up

Tested on Linux with CPython 3.12.14. Use Python 3.12 or later, Bash, a text editor, mktemp, rm and rmdir. The example needs no network access. Run the steps in the same terminal and stop if setup fails. Run Python without -O so the assertions stay enabled.

start_dir="$PWD"
work_dir="$(mktemp -d)" || exit 1
cd -- "$work_dir" || exit 1

Run the example

Save this as merge_sorted_streams.py:

import heapq

left = [1, 7, 3]
right = [2, 4, 8]
unchecked = list(heapq.merge(left, right))
print("unchecked:", unchecked)
print("globally sorted:", unchecked == sorted(unchecked))
ordered = list(heapq.merge(sorted(left), sorted(right)))
print("sorted inputs:", ordered)
descending = list(heapq.merge([7, 3, 1], [8, 4, 2], reverse=True))
print("descending:", descending)
assert ordered == [1, 2, 3, 4, 7, 8]
assert descending == [8, 7, 4, 3, 2, 1]

Run:

python3 -B merge_sorted_streams.py

Observed output:

unchecked: [1, 2, 4, 7, 3, 8]
globally sorted: False
sorted inputs: [1, 2, 3, 4, 7, 8]
descending: [8, 7, 4, 3, 2, 1]

Treat input ordering as a producer contract

The heapq.merge documentation requires inputs already sorted in the requested direction. The function chooses among the current items from those inputs; it does not sort each input or reject a later out-of-order item.

For these small lists, sorted repairs each producer before merging. That allocates complete sorted lists. A streaming pipeline should establish ordering upstream, such as an explicitly ordered database query. If consumers must never observe partial output before an ordering error, a lazy validation check alone is insufficient: it can discover a late error after earlier records have been consumed.

Limits

Use reverse=True only with inputs that are already descending. When using key, all producers must use the same ordering key and direction. The merge iterator avoids loading all input records at once, but this example calls list for display and therefore materializes the result. Sorting and comparisons can still fail for incompatible values.

Clean up

Remove the example file and the temporary directory:

rm -- merge_sorted_streams.py
cd -- "$start_dir" || exit 1
rmdir -- "$work_dir"
unset start_dir work_dir

Acknowledgements

This post was created with assistance from AI.

Last updated on