Middle · Algorithms

Merge sorted streams

How do you merge two sorted inputs without re-sorting them?

Try explaining this aloud before opening the answer. State your assumptions and trace a boundary case.

ALGORITHM LAB · STEP THROUGH THE INVARIANT

Input scenario

[1, 4, 8] + [2, 4, 7]

STEP 1 / 7

Two unread heads

Left

Right

Output

∅ Empty

Choose left first on equal values to preserve cross-source stability.

Computed traces for these inputs. Indexes identify cell positions; active cells are labeled as well as highlighted. Compare a boundary case using the scenario selector. No code is sent to a server.

EXAMPLE · FRAGMENT UNLESS A COMPLETE PROGRAM IS SHOWN

func Merge(a, b []int) []int {
	out := make([]int, 0, len(a)+len(b))
	i, j := 0, 0
	for i < len(a) && j < len(b) {
		if a[i] <= b[j] {
			out = append(out, a[i])
			i++
		} else {
			out = append(out, b[j])
			j++
		}
	}
	out = append(out, a[i:]...)
	return append(out, b[j:]...)
}

Reveal a strong answer

Track the next unread element of each input. Emit the smaller and advance only its pointer, preserving the invariant that the output prefix is sorted and contains exactly the consumed elements.
When one input is exhausted, append or stream the remainder. Decide tie ordering: choosing the left element first preserves stability across the two sources. Never assume both inputs have equal length.
For k streams, keep one head per nonempty stream in a min-heap. For remote streams, also bound buffering and close every iterator on cancellation; algorithmic complexity does not describe network lifetime.

Common trap

Concatenate-and-sort adds unnecessary work and cannot naturally stream an unbounded input.

Complexity & use

Two inputs: O(n+m) time, O(n+m) output. k streams: O(N log k) time with O(k) heap state.

Try it

Merge [1,4,8] and [2,4,7], retaining left-before-right ties.

Worked solution

Emit1,2,4(left),4(right),7,8. Test one empty source and all-equal values. If the caller needs source stability, include source identity in the tie rule.

Change the constraint

What would you do if an input violates its promised sorted order halfway through?

How did you do?

Self-assessment, not a compiler pass or interview score. Explain the reasoning unaided before marking understood.

Not marked. Progress stays on this browser, separate from course completion.

Primary references

Checked 2026-10-20. Use documentation for your pinned runtime, driver and tool version.