How do you merge two sorted arrays? | Interview Question

Q: How do you merge two sorted arrays?

**Target Audience:** Beginners preparing for coding interviews — you only need to know Python lists and loops. **Difficulty:** Easy **Language:** Python 3 > **How to read this doc:** Each idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the word an interviewer expects. Every program here was run with `python3`, and the output shown in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First Two teachers have each sorted their own pile of exam papers by score, lowest on top. The head teacher wants **one** pile, also sorted. You could throw both piles on the floor and sort all the papers again from scratch, but that ignores the work the teachers already did. The smarter way: put the two piles side by side, look only at the **top paper of each pile**, take the lower one and put it on the new pile, and repeat. You never need to look deeper than the top of each pile, because everything underneath is a

The problem

Question presented to candidate: "You are given two lists of integers, each already sorted in ascending order. Write a Python function that returns one sorted list containing every element of both. Then tell me how you would do it if the first list had empty slots at the end and I wanted the merge done in place."

What a strong answer should cover:

The two-pointer merge: compare the fronts, append the smaller, advance that pointer, then add the leftovers of whichever list is not used up.
O(m + n) time and O(m + n) output space, compared with O((m + n) log(m + n)) for re-sorting from scratch.
Using <= so equal items from the first list come first (a stable merge), and why that matters for records.
The in-place variant (LeetCode 88): fill nums1 from the back so nothing unread is overwritten; O(1) extra space.
Python specifics: result.extend(a[i:]) copies the tail (slicing makes a copy), heapq.merge exists and returns a lazy generator, and sorted(a + b) is correct but does more work than needed.

Clarifying questions expected:

"New list, or merge into the first list in place?"
"Can either list be empty, and can there be duplicates?"

Code / implementation expected: Yes — a Python merge(a, b) with two indices, and ideally the from-the-back in-place version.

sorting
merge

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you only need to know Python lists and loops. Difficulty: Easy Language: Python 3

How to read this doc: Each idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the word an interviewer expects. Every program here was run with python3, and the output shown in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

Two teachers have each sorted their own pile of exam papers by score, lowest on top. The head teacher wants one pile, also sorted. You could throw both piles on the floor and sort all the papers again from scratch, but that ignores the work the teachers already did.

The smarter way: put the two piles side by side, look only at the top paper of each pile, take the lower one and put it on the new pile, and

The solution is hidden so you can try first

7 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonTwo-pointer merge into a new array (several inputs, including empty ones)

Practice

PythonIn-place merge into nums1 by filling from the back

Practice

PythonStability (<= vs <) and counting comparisons

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.