021. Merge Two Sorted Arrays

Foundation · Download this solution · All solutions and shared helpers

Problem

Merge two nondecreasing integer lists into a new nondecreasing list containing every occurrence. Neither input is modified. Empty inputs are allowed. When equal values meet, consume from a first; this makes the merge stable with respect to the two source streams.

Examples

Example 1

merge_sorted([1, 4, 7], [2, 3, 9])
=> [1, 2, 3, 4, 7, 9]

Each smaller frontier is consumed.

Example 2

merge_sorted([], [2, 2])
=> [2, 2]

All remaining values come from b.

Example 3

merge_sorted([1, 1], [1])
=> [1, 1, 1]

Multiplicity is retained.

Reveal the worked solution and reasoning

Why this mechanism works

Only the first unread value of each sorted source can be its next contribution. Compare those two frontier values and consume the smaller one. Once a source is exhausted, the other unread suffix is already sorted and can be appended without more comparisons.

State and boundaries

i and j are unread boundaries in a and b. output is the sorted merge of the consumed prefixes.

Protocol

Start both boundaries at zero.
Compare while both sources have candidates.
Append the smaller frontier and advance only its source.
Append either remaining suffix.
Return output.

Visualization

a: [1 | 4,7]
b: [2,3,9]
output: [1] -> compare 4 with 2

Python implementation

def merge_sorted(a, b):
    i = j = 0
    output = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            output.append(a[i])
            i += 1
        else:
            output.append(b[j])
            j += 1
    output.extend(a[i:])
    output.extend(b[j:])
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

merge_sorted([1, 4, 7], [2, 3, 9])

L2 merge_sorted: i = j = 0
a=[1, 4, 7]; b=[2, 3, 9]; i=0; j=0

L3 merge_sorted: output = []
a=[1, 4, 7]; b=[2, 3, 9]; i=0; j=0; output=[]

L6 merge_sorted: output.append(a[i])
a=[1, 4, 7]; b=[2, 3, 9]; i=0; j=0; output=[1]

L7 merge_sorted: i += 1
a=[1, 4, 7]; b=[2, 3, 9]; i=1; j=0; output=[1]

L9 merge_sorted: output.append(b[j])
a=[1, 4, 7]; b=[2, 3, 9]; i=1; j=0; output=[1, 2]

L10 merge_sorted: j += 1
a=[1, 4, 7]; b=[2, 3, 9]; i=1; j=1; output=[1, 2]

L9 merge_sorted: output.append(b[j])
a=[1, 4, 7]; b=[2, 3, 9]; i=1; j=1; output=[1, 2, 3]

L10 merge_sorted: j += 1
a=[1, 4, 7]; b=[2, 3, 9]; i=1; j=2; output=[1, 2, 3]

... 1 intermediate state changes omitted ...

L7 merge_sorted: i += 1
a=[1, 4, 7]; b=[2, 3, 9]; i=2; j=2; output=[1, 2, 3, 4]

L6 merge_sorted: output.append(a[i])
a=[1, 4, 7]; b=[2, 3, 9]; i=2; j=2; output=[1, 2, 3, 4, 7]

L7 merge_sorted: i += 1
a=[1, 4, 7]; b=[2, 3, 9]; i=3; j=2; output=[1, 2, 3, 4, 7]

L12 merge_sorted: output.extend(b[j:])
a=[1, 4, 7]; b=[2, 3, 9]; i=3; j=2; output=[1, 2, 3, 4, 7, 9]

Result: [1, 2, 3, 4, 7, 9]. Each smaller frontier is consumed.

merge_sorted([], [2, 2])

L2 merge_sorted: i = j = 0
a=[]; b=[2, 2]; i=0; j=0

L3 merge_sorted: output = []
a=[]; b=[2, 2]; i=0; j=0; output=[]

L12 merge_sorted: output.extend(b[j:])
a=[]; b=[2, 2]; i=0; j=0; output=[2, 2]

Result: [2, 2]. All remaining values come from b.

Why the solution is correct

The smaller frontier is no larger than any remaining value in either sorted source, so appending it preserves order. Each advance consumes exactly one occurrence. Tail copying finishes the remaining occurrences without changing order.

Time and space

O(n+m) time and O(n+m) output space; suffix slicing also creates temporary copies of at most that size.

Common mistakes

Advancing both pointers drops an unconsumed value. Forgetting the tail loses everything after the shorter input ends.

Reasoning card

State: i and j are unread boundaries in a and b. output is the sorted merge of the consumed prefixes.

Invariant: Output is sorted and contains all consumed prefixes.

Decision to rehearse: Advance only the source whose item was consumed.

Finish: Return output

Transfer exercise

Merge into spare capacity at the end of a. Explain why writing from the back protects unread input.