Merge Sorted Array · Optimal Solution

Fill from the back. No overwrites.

Two sorted card stacks need to combine into one — but the first stack sits on a tray with just enough empty slots at the end to fit both. Filling from the back avoids overwriting unread cards: compare the largest remaining card from each stack, place the winner at the tail, and decrement. When one stack is exhausted, the other is already in position. O(n + m) time. O(1) space.

Interactive

Watch the algorithm run

Edge Cases

Why Backward?

Understanding boundary behavior is as important as the main algorithm path.

Secondary is empty

n = 0 means there is nothing to merge. The primary array is already the final result.

Primary is empty

m = 0 means the primary buffer is all zeros. Every secondary element is copied in, largest first.

Algorithm

Algorithm

Filling from the back guarantees no element is overwritten before it is read. The largest values land at the end first.

  1. 1

    Set three pointers

    Place p at the end of the valid primary elements (m − 1), s at the end of the secondary array (n − 1), and w at the very end of the primary array (m + n − 1).

  2. 2

    Compare and write

    Compare primary[p] with secondary[s]. Write the larger value at primary[w], then decrement the source pointer and w.

  3. 3

    Drain the secondary

    Continue until s < 0. If primary elements remain, they are already in place — no further work is needed.

Edge Cases

Edge Patterns

Secondary exhausted first — remaining primary elements are already sorted in place. No further work needed.

Primary exhausted first — remaining secondary elements fill the front positions without comparison.

All elements from one side — one pointer sweeps while the other stays put. Still O(m+n) total steps.

Complexity

Complexity

Time: O(m + n) — each element placed exactly once.
Space: O(1) — merge happens in-place in the primary array.