skip to content

Merging a sorted batch into a pre-sized buffer that already holds sorted data — why write from the back?

level: seniorimportance: should knowfreq 55%

answer

  1. one buffer plays two roles
  2. where does the spare capacity sit?
  3. compare the write index with the unread reads
  4. the write cursor is i plus j
  5. writes must land in vacated slots

basics

~20 s

Writing front-to-front, the write cursor catches up to entries not yet read: the first time the incoming batch wins a comparison, the write lands on a live slot and destroys it. Descending from the back keeps every write inside vacated space.

solid answer

~50 s

The buffer plays two roles at once — it is both a source and the destination — so the only rule that matters is that writes must land in slots the reads have already vacated. Ascending, the write position equals `i + j` while the unread settled entries begin at `i`, so the writer sits at or beyond the reader and clobbers live data as soon as one incoming record is taken. Descending, with `i` and `j` on the last unread entry of each side and the writer at `i + j + 1`, the writer stays strictly above `i` while both sides are live, and everything above `i` is vacated or spare. The tails are asymmetric too: when the batch runs out, the remaining settled entries are already in place; when the settled side runs out, the rest of the batch must still be copied down.

code

pseudocode · 14 lines
pseudocode
// buf[0..m-1] holds settled trades in key order; buf has capacity m + k
// inc[0..k-1] is the sorted incoming batch
i = 0    // reads settled trades inside buf
j = 0    // reads the incoming batch
w = 0    // writes into buf
while i < m and j < k
    if buf[i].key <= inc[j].key
        buf[w] = buf[i]
        i = i + 1
    else
        buf[w] = inc[j]
        j = j + 1
    w = w + 1
...

go deeper

for a junior

Recognise that when the output shares storage with one of the inputs, the order of writes matters. Be able to say that writing forward can land on data that has not been read yet.

for a middle

Work the index arithmetic: show where the write cursor sits relative to the unread read cursor in each direction, and trace a three-element example that loses an entry.

for a senior

Catch this in review without running it, name both tail cases and their asymmetry, and check the tie-breaking rule against the required equal-key ordering before approving the change.

for a principal

Weigh the in-place merge against a fresh output buffer for the team: one saves a linear allocation, the other removes a whole class of aliasing defects that tests with distinct keys will never surface.

## The situation under review A settlement buffer holds the day's already-settled trades in key order in its first `m` slots, and it was allocated with room for `m + k`. A sorted incoming batch of `k` trades must be merged into it. The tempting shape is the merge everyone has written a hundred times: two read cursors, one write cursor, all starting at zero and moving up. That version is wrong here, and the reason is not stylistic. ## Why the buffer being both source and destination changes everything When the destination is a separate array, reads and writes never interact and any direction works. Here the destination **aliases** one of the sources. The single governing rule becomes: > Every write must land on a slot that is either spare capacity or has already been read. Check the ascending version against that rule with index arithmetic. If `i` entries have been taken from the settled side and `j` from the batch, then `i + j` entries have been written, so the write cursor sits at `w = i + j`, while the next unread settled entry is at index `i`. Since `j >= 0`, we get `w >= i` — the writer is at or beyond the reader. Equality holds only while `j == 0`; the instant one incoming trade is taken, `w` moves past `i` and the next write overwrites a settled trade nobody has read. Now the descending version. Let `i` be the last unread settled index and `j` the last unread batch index, counting down. The number of entries still to be placed is `i + j + 2`, and they must fill the buffer's top slots, so the write cursor is `w = i + j + 1`. With `j >= 0` this gives `w >= i + 1 > i` strictly, for as long as both sides are live. Every write lands above `i`, and everything above `i` is either spare capacity or a slot whose original occupant was already moved. The invariant holds by construction, without any bookkeeping. ## A concrete corruption trace Settled keys `[10, 30]` in a buffer of capacity 3, incoming batch `[20]`. Ascending: `i=0, j=0, w=0`. `10 <= 20`, so slot 0 receives 10 — harmless, it was already there. Now `i=1, w=1`. Compare `30` with `20`: the batch wins, so slot 1 receives 20 — **and 30, which nobody has read, is gone**. The batch is exhausted, the loop ends, and the leftover settled entry at index 1 is copied up to slot 2, producing `[10, 20, 20]`. A trade vanished and another was duplicated, with no crash and no error to log. Descending: `i=1, j=0, w=2`. `30 > 20`, so slot 2 receives 30; `i=0, w=1`. Now `10 <= 20`, so the batch entry is taken: slot 1 receives 20; the batch is exhausted, `w=0`. The remaining settled entry at index 0 is already exactly where it belongs, so nothing further is needed. Result `[10, 20, 30]`. ## The two tails are not symmetric This is the second thing a reviewer checks. When the **batch** is exhausted first, the untouched settled entries occupy a prefix that is already in final position — copying them would be a self-copy, and stopping is correct. When the **settled** side is exhausted first, the remaining batch entries have never been placed and must all be copied into the low slots. Code that treats both tails the same way is wrong in one direction or does useless work in the other, and dropping the second tail is a silent data-loss bug of exactly the kind that survives a happy-path test. ## Ties, and whether the merge stays stable A descending merge fills the **highest** positions first, which inverts the usual tie-breaking rule. If the contract is that among equal keys the already-settled entries precede the incoming ones, then on a tie the descending merge must take from the **incoming** side first, because whatever is written first ends up further right. Concretely, the comparison becomes "take the settled entry only when its key is strictly greater". A merge that copies the tie-breaking rule from an ascending implementation reverses the order of equal keys — invisible in a test with distinct keys, and a real defect when the key is a timestamp and the payloads differ. ## What to say in the review Three lines are enough: the destination aliases a source; the ascending write cursor reaches unread slots as soon as the batch wins a comparison, so a trade is lost; descend instead, with all three cursors at the top, and the write always lands in vacated space. If the extra memory is affordable, the alternative is equally valid and easier to review: merge ascending into a **fresh** buffer of size `m + k`, where no aliasing exists at all. It costs an additional linear allocation and one linear copy, both of which are typically invisible next to the work of parsing and persisting the batch. The in-place merge earns its place when the buffer is deliberately pre-sized and the allocation is the thing being avoided; it does not earn its place merely because it feels tighter. ## The transferable heuristic Whenever source and destination share storage, ask which region the writes enter. The direction that puts the write cursor into space the reads have already left is the correct one — that is the same argument that lets a collapsing sweep write behind its scanner, applied to a case where the safe direction happens to be backwards.

  • When the back-to-front merge exhausts the incoming batch first, what work remains?
    None. The settled entries that were never touched still sit in the buffer's low slots, and those are exactly their final positions, so the loop can stop the moment the batch cursor falls off the front. The opposite tail is not symmetric: if the settled side empties first, every remaining batch entry still has to be copied down, and forgetting that tail loses records silently.
  • Would merging into a freshly allocated buffer remove the hazard, and what does it cost?
    Yes — with no aliasing between source and destination, any direction is safe and the ascending version reads more naturally. The cost is one extra allocation of the combined size plus one linear copy, and a decision about who owns the old buffer afterwards. Asymptotics are identical; you are trading a linear amount of memory for a merge that is far harder to get wrong in review.
  • Does a descending merge preserve the relative order of entries with equal keys?
    Only if the tie-breaking is inverted along with the direction. Descending writes fill the highest slots first, so whichever side is taken on a tie ends up later. To keep settled entries ahead of incoming ones among equal keys, the settled side must be taken only when its key is strictly greater. Reusing an ascending comparison here quietly reverses equal-key order.

saying these in an interview costs you the question

  • Calls the merge direction a style choice, either way works
  • Assumes reads and writes are safe because they use different names
  • Copies the settled entries aside first and still calls it in-place
  • Stops the merge when the settled side empties, dropping the batch tail
  • Reuses the ascending tie-break rule and reverses equal-key order
  • Relies on a happy-path test with distinct keys to catch the overwrite

context

resolving links…