Python heapq.merge: check that every input is already sorted
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 1Run 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.pyObserved 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_dirAcknowledgements
This post was created with assistance from AI.