In a k-way merge heap, what ordering is guaranteed among equal keys from different sources?

## Two different questions hiding in one When someone asks "is a k-way merge stable?", they are usually conflating two claims: 1. Do elements from the *same* source keep their relative order? 2. Do equal-keyed elements from *different* sources come out in a predictable order? The answers differ, and saying so is most of the credit. ## Within a source: preserved, and for free A source contributes at most one entry to the heap at a time. Its element at position p+1 is only inserted after the element at position p has been extracted and emitted. So p can never be emitted after p+1 — the structure makes it impossible, no matter how the heap reorders internally. You get per-source order preservation without asking for it and without any tie-break machinery. ## Across sources: nothing is promised A binary heap satisfies only the heap property: every parent is no greater than its children. Among equal keys that property says nothing about which one reaches the root first. When two equal keys sit in the heap, which one is extracted depends on their array positions, and those positions are a product of the insertion order, the sift-up path taken on insert, and the last-element promotion done on every extraction. It is deterministic in the mechanical sense — the same operation sequence gives the same result — but it is not *meaningful*, and it is fragile: seed the sources in a different order, or process one file slightly ahead of another, and the tie flips. For a merged fleet log this shows up concretely. Two hundred servers emit lines stamped to the millisecond; collisions are constant. Rerun the merge after re-listing the input directory and the output differs on exactly those lines. Anything that diffs feeds, checksums them, or asserts on them in tests now fails intermittently for a reason that looks like a bug in the merge and is not. ## The fix: make ties impossible Do not try to make the heap stable — extend the key so there are no ties to break. Compare on a composite key: `(timestamp, source rank, position within source)` The first field is the real ordering. The second breaks equal timestamps by a stable, meaningful source rank — server identifier, shard number, whatever your operators expect. The third can never tie for two entries with the same source rank, because a source has at most one live entry, so the composite is a **total order**. With a total order, the heap's internal tie-breaking never gets a chance to matter, and the output is byte-identical on every run regardless of read order. A detail worth stating: the choice of second field is a product decision, not a technical one. Ranking by server name gives you a feed where simultaneous lines are grouped by host; ranking by ingestion order gives you a feed that reflects arrival. Both are defensible; the requirement is that you *chose* one, not that the heap chose for you. ## Anti-patterns - **"Sort the merged output afterwards to fix ordering."** That costs `O(N log N)`, needs the whole feed resident, and defeats the entire reason you merged with a heap. It also does not help unless the sort's own tie handling is defined. - **"Add a global monotonic counter as the tie-break."** Attractive but wrong here: assigning counters at insertion time makes the tie-break depend on the interleaving of insertions, which is exactly the non-determinism you were trying to remove. The counter must come from the data (position within a known source), not from the merge's own timing. - **"Heaps are stable if you insert in order."** They are not. Insertion order affects the outcome but does not preserve it; extraction promotes the last array element to the root and sifts it down, which reshuffles equal keys arbitrarily. - **"Ties don't matter, the timestamps are unique."** Nearly always false at fleet scale: clock resolution is coarser than event rate, clocks skew, and a single millisecond can hold thousands of lines across 200 hosts. Design for ties. ## What good sounds like "Within a source, order is preserved by construction. Across sources, nothing is promised — a heap is not stable and ties resolve by array position, so the feed is not reproducible. I would make the comparison key a composite of timestamp, then source rank, then position, which gives a total order and therefore a deterministic feed; and I would pick the source rank to match what operators expect to see grouped." That answer distinguishes the two guarantees, names the mechanism, gives the fix, and treats the tie-break as a product choice rather than an implementation detail.