heapq.merge output in a nightly pipeline arrives out of order and downstream silently truncates - what went wrong?

### What merge actually promises The docstring is explicit: `heapq.merge` is "similar to `sorted(itertools.chain(*iterables))` but returns a generator, does not pull the data into memory all at once, and **assumes that each of the input streams is already sorted**." That last clause is a precondition, and it is enforced by nobody. Mechanically, the function keeps one pending element per input and repeatedly yields the smallest of those, then advances that input by one. That interleaving is correct precisely when each input is monotonically non-decreasing. Feed it an input that is not, and the output is whatever the interleaving produces: ```python list(heapq.merge([3, 1], [2])) # [2, 3, 1] ``` No exception. No warning. Just a stream whose ordering silently breaks at element three. ### Why this becomes a silent truncation Downstream consumers of an ordered stream are often written to exploit the ordering: they process while coordinates advance and stop, or flush and finish, when they see a value that goes backwards — either as a deliberate sentinel or because a sorted-merge-join style step has nothing left to match. So the failure does not present as "the output was mis-ordered". It presents as "the nightly run produced a file with a third of the expected records and exited zero". Every stage reports success. The corruption entered at a producer several steps upstream that emitted one region's intervals in file order rather than coordinate order. This is the shape of failure worth naming in an interview: a precondition that is cheap to state, cheap to check, and checked nowhere, turning a data defect into a plausible-looking result rather than a crash. ### Diagnosing it The merged output is the wrong place to look, because by then you cannot tell which source misbehaved. Instrument the inputs instead. A checking generator costs one comparison per element and names the offending source: ```python def checked(source, name): previous = None for item in source: if previous is not None and item < previous: raise ValueError(f"{name} went backwards at {item!r}") previous = item yield item merged = heapq.merge(*(checked(s, n) for s, n in sources)) ``` Because `merge` is lazy, wrapping the inputs preserves the streaming behaviour: nothing is materialised, and the error fires at the first offending record rather than at the end. If the check must use the same ordering rule as the merge, apply the same `key` function inside it. ### The parameters, and their limits `key=` supplies the ordering function, exactly as `sorted` does, and — importantly — `merge` yields the **original** elements, not decorated ones. `reverse=True` merges descending inputs into a descending output. Both were added in **Python 3.5**. The limitation people trip over: `reverse` is a property of the whole call, not of an input. You cannot merge one ascending and one descending source. Reverse the offending one first, or re-sort it. Likewise there is one `key` for all inputs, so heterogeneous records must be normalised into a comparable shape before they reach the call. ### Merge versus sorting the concatenation `sorted(itertools.chain(*iterables))` is the correct-under-all-conditions alternative: it does not care about input order because it sorts. What it costs is memory — every record materialised in one list before the first result appears — and it forfeits early termination, since you cannot take the first hundred results without producing all of them. `heapq.merge` holds one pending element per input plus the small structure that orders them, so its footprint scales with the *number* of inputs rather than their length. That is what makes it the right tool for merging many large pre-sorted files, and it is exactly why the precondition matters: the whole reason to use it is that you are not going to look at all the data at once. So the answer to "what went wrong" has two halves. The proximate cause is an unsorted input. The systemic cause is that a streaming merge was adopted for its memory profile without adopting the boundary check that makes its precondition enforceable — and in a long batch run, an unenforced precondition is discovered by whoever reads the output, not by the process that produced it.