Loading…

easyBasicsSometimes asked

Merge Two Sorted Arrays

Basics · 6 min

Given two arrays a and b, each sorted in non-decreasing order, return a single sorted array containing all their elements.

In plain English

Two pointers walk both arrays, always copying the smaller current element first.

Examples

Example 1

Input: a = [1, 3, 5], b = [2, 4]
Output: [1, 2, 3, 4, 5]
Note: Interleaved in order.

Example 2

Input: a = [], b = [1, 2]
Output: [1, 2]
Note: One side empty.

Example 3

Input: a = [1, 1], b = [1]
Output: [1, 1, 1]
Note: Duplicates kept.

Constraints

0 ≤ a.length, b.length ≤ 10^5
Both inputs sorted

Clarifying questions2First question: Are both inputs guaranteed sorted?Explore questions

Q1.Are both inputs guaranteed sorted?
Yes — that's what makes the linear merge valid.
Q2.Must duplicates be preserved?
Yes; I use `<=` for stability.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Merge with two pointers: compare `a[i]` and `b[j]`, append the smaller, advance that pointer. When one runs out, append the rest of the other. O(n+m).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you exploit existing sortedness with a two-pointer merge instead of re-sorting.

Where candidates slip

Re-sorting the concatenation, or dropping the remainder.

How to stand out

Identify it as merge sort's merge step and discuss in-place merging (LC88).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Two-pointer merge

TimeO(n + m)SpaceO(n + m)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Both arrays are sorted — what's the cheapest way to combine them?

2Hint 2Explore hint

Compare the two front elements; take the smaller and advance that pointer.

3Hint 3Explore hint

When one runs out, append the rest of the other.

A · Core idea

Because both inputs are already sorted, you can merge them in linear time with two pointers: repeatedly take the smaller of the two current fronts and advance that pointer. This is the merge step of merge sort.

Why it's linear, not n log n. Re-concatenating and sorting throws away the sortedness you already have and costs O((n+m)log(n+m)). The two-pointer merge exploits the existing order — each element is emitted exactly once, so it's O(n+m).

Why advance only the consumed pointer. You output one element per step (the smaller front) and move only that array's pointer; the other front is still the smallest unprocessed value on its side, ready for the next comparison.

Stability and leftovers. Use a[i] <= b[j] (not <) so equal elements keep a's-before-b's order and none are dropped. When one array empties, append the entire remainder of the other — that tail is already sorted.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [1, 3, 5], b = [2, 4]

1 vs 2

1 smaller

Stateout=[1], i=1

Final result[1, 2, 3, 4, 5]

C · Code with teaching comments

solution.javaJava

Two-pointer merge — optimal

2 teaching notes

1
public int[] merge(int[] a, int[] b) {
2
    int[] out = new int[a.length + b.length];
3
    int i = 0, j = 0, k = 0;
4
    while (i < a.length && j < b.length) {
5
        // Append the smaller front and advance only that pointer.
6
        out[k++] = a[i] <= b[j] ? a[i++] : b[j++];
7
    }
8
    while (i < a.length) out[k++] = a[i++];
9
    while (j < b.length) out[k++] = b[j++];
10
    return out;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n + m) timeO(n + m) spaceOpen the invariant and proofExplore the proof

Re-sorting the concatenation is O((n+m)log(n+m)); the linear merge exploits the existing sortedness.

ComplexityO(n + m) time, O(n + m) space — each of the n+m elements is emitted once with O(1) work; the output array is O(n+m) space.

E · Edge cases and pitfalls5a = [], b = [1, 2] — One side empty — just copy the other.Explore edge cases

Edge cases handled

a = [], b = [1, 2]One side empty — just copy the other.
a = [1, 1], b = [1]Duplicates kept → [1, 1, 1].
a = [1,2,3], b = [4,5]No interleave needed; a then b.

Pitfalls

Forgetting to copy the leftovers after one pointer is exhausted.
Using `<` instead of `<=` and dropping or reordering equal elements.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[] merge(int[] a, int[] b) { int[] out = new int[a.length + b.length]; int i = 0, j = 0, k = 0; while (i < a.length && j < b.length) { out[k++] = a[i] <= b[j] ? a[i++] : b[j++];Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting to copy the leftovers after one pointer is exhausted.
Using `<` instead of `<=` and dropping/duplicating equal elements (stability).

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-pointer merge

Code pattern to memorize

while i<n and j<m: out += smaller(a[i],b[j]); advance; then drain

Rules to remember

1Append the smaller front.
2Advance only the consumed pointer.
3Drain the remainder.

Use this pattern when

Combining sorted sequences
Merge step of merge sort / k-way merge

Choose another pattern when

Inputs unsorted — sort first or use a different method

Interview takeaway

Merging sorted inputs is linear — never re-sort.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Two-pointer merge. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Merge Sorted Array (in place)
Coming soon
Merge from the back to do it in O(1) extra space.
Merge Sort
Coming soon
This merge is the combine step of the full sort.

Same pattern

easyBasicsSometimes asked

Merge Two Sorted Arrays

Basics · 6 min

Given two arrays a and b, each sorted in non-decreasing order, return a single sorted array containing all their elements.

In plain English

Two pointers walk both arrays, always copying the smaller current element first.

Examples

Example 1

Input: a = [1, 3, 5], b = [2, 4]
Output: [1, 2, 3, 4, 5]
Note: Interleaved in order.

Example 2

Input: a = [], b = [1, 2]
Output: [1, 2]
Note: One side empty.

Example 3

Input: a = [1, 1], b = [1]
Output: [1, 1, 1]
Note: Duplicates kept.

Constraints

0 ≤ a.length, b.length ≤ 10^5
Both inputs sorted

Clarifying questions2First question: Are both inputs guaranteed sorted?Explore questions

Q1.Are both inputs guaranteed sorted?
Yes — that's what makes the linear merge valid.
Q2.Must duplicates be preserved?
Yes; I use `<=` for stability.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Merge with two pointers: compare `a[i]` and `b[j]`, append the smaller, advance that pointer. When one runs out, append the rest of the other. O(n+m).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you exploit existing sortedness with a two-pointer merge instead of re-sorting.

Where candidates slip

Re-sorting the concatenation, or dropping the remainder.

How to stand out

Identify it as merge sort's merge step and discuss in-place merging (LC88).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Two-pointer merge

TimeO(n + m)SpaceO(n + m)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Both arrays are sorted — what's the cheapest way to combine them?

2Hint 2Explore hint

Compare the two front elements; take the smaller and advance that pointer.

3Hint 3Explore hint

When one runs out, append the rest of the other.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

a = [1, 3, 5], b = [2, 4]

1 vs 2

1 smaller

Stateout=[1], i=1

Final result[1, 2, 3, 4, 5]

C · Code with teaching comments

solution.javaJava

Two-pointer merge — optimal

2 teaching notes

1
public int[] merge(int[] a, int[] b) {
2
    int[] out = new int[a.length + b.length];
3
    int i = 0, j = 0, k = 0;
4
    while (i < a.length && j < b.length) {
5
        // Append the smaller front and advance only that pointer.
6
        out[k++] = a[i] <= b[j] ? a[i++] : b[j++];
7
    }
8
    while (i < a.length) out[k++] = a[i++];
9
    while (j < b.length) out[k++] = b[j++];
10
    return out;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n + m) timeO(n + m) spaceOpen the invariant and proofExplore the proof

Re-sorting the concatenation is O((n+m)log(n+m)); the linear merge exploits the existing sortedness.

ComplexityO(n + m) time, O(n + m) space — each of the n+m elements is emitted once with O(1) work; the output array is O(n+m) space.

E · Edge cases and pitfalls5a = [], b = [1, 2] — One side empty — just copy the other.Explore edge cases

Edge cases handled

a = [], b = [1, 2]One side empty — just copy the other.
a = [1, 1], b = [1]Duplicates kept → [1, 1, 1].
a = [1,2,3], b = [4,5]No interleave needed; a then b.

Pitfalls

Forgetting to copy the leftovers after one pointer is exhausted.
Using `<` instead of `<=` and dropping or reordering equal elements.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting to copy the leftovers after one pointer is exhausted.
Using `<` instead of `<=` and dropping/duplicating equal elements (stability).

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-pointer merge

Code pattern to memorize

while i<n and j<m: out += smaller(a[i],b[j]); advance; then drain

Rules to remember

1Append the smaller front.
2Advance only the consumed pointer.
3Drain the remainder.

Use this pattern when

Combining sorted sequences
Merge step of merge sort / k-way merge

Choose another pattern when

Inputs unsorted — sort first or use a different method

Interview takeaway

Merging sorted inputs is linear — never re-sort.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Two-pointer merge. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Merge Sorted Array (in place)
Coming soon
Merge from the back to do it in O(1) extra space.
Merge Sort
Coming soon
This merge is the combine step of the full sort.

Same pattern