Merge Two Sorted Arrays
Table of Contents + −
This one looks easy. You have two arrays. Both are already sorted. The interviewer asks you to join them into one sorted array. The real test is whether you use the fact that both arrays are already sorted. If you ignore that and just sort everything again, you throw away free information. So this question is really checking whether you can spot the two-pointer idea.
🔄 The Problem
You get two arrays. Both are sorted in increasing order. You have to return a single array that holds every element from both, still sorted.
Input: a = [1, 3, 5, 7] b = [2, 4, 6, 8]Output: [1, 2, 3, 4, 5, 6, 7, 8]The two arrays do not have to be the same size. One can be longer than the other. That is fine.
🐢 The Simple Approach (and why it is wasteful)
The first idea that comes to mind is simple. Put everything from both arrays into one big array. Then sort that big array. Done.
It works. It gives the right answer. But think about what you just did. Sorting a list of n + m items costs about O((n + m) log(n + m)) time. You paid for a full sort. But your inputs were already sorted. So you did all that work for nothing.
So the interviewer nods, then asks the real question. “Can you do it without sorting again?”
⚡ The Optimal Approach: Two Pointers
Here is the better idea. Walk through both arrays at the same time using two pointers. A pointer here just means an index. It is a number that says “I am looking at this position right now.”
Put one pointer at the start of array a and one at the start of array b. Now compare the two elements they point at. The smaller one goes into the result first. Then move that pointer forward by one. Keep doing this.
See why this works? Both arrays are sorted. So the smallest element you have not used yet is always sitting at one of the two pointers. You never have to look further back. You just keep picking the smaller front element.
Let us walk it through with a = [1, 3, 5, 7] and b = [2, 4, 6, 8].
Compare 1 and 2 -> take 1 result: [1]Compare 3 and 2 -> take 2 result: [1, 2]Compare 3 and 4 -> take 3 result: [1, 2, 3]Compare 5 and 4 -> take 4 result: [1, 2, 3, 4]Compare 5 and 6 -> take 5 result: [1, 2, 3, 4, 5]Compare 7 and 6 -> take 6 result: [1, 2, 3, 4, 5, 6]Compare 7 and 8 -> take 7 result: [1, 2, 3, 4, 5, 6, 7]b is empty, copy rest of a result: [1, 2, 3, 4, 5, 6, 7, 8]At some point one array runs out. When that happens, the other array still has elements left, and they are already sorted. So you just copy them straight to the end of the result. No more comparing needed.
This is exactly the merge step inside merge sort. If you learn it well here, you basically learn the heart of merge sort for free.
Steps to merge two sorted arrays
- Make an empty result array. Set pointer
ito 0 for arrayaand pointerjto 0 for arrayb. - While both pointers are still inside their arrays, compare
a[i]andb[j]. - Take the smaller one. Put it in the result. Move that pointer forward by one.
- When one array runs out, copy every leftover element from the other array into the result.
- Return the result.
# Merge two sorted lists into one sorted listdef merge(a, b): result = [] i, j = 0, 0
# Pick the smaller front element while both have items left while i < len(a) and j < len(b): if a[i] <= b[j]: result.append(a[i]) i += 1 else: result.append(b[j]) j += 1
# Copy whatever is left result.extend(a[i:]) result.extend(b[j:]) return result
a = [1, 3, 5, 7]b = [2, 4, 6, 8]print(merge(a, b))The output of the above code will be:
[1, 2, 3, 4, 5, 6, 7, 8]⏱️ Time and Space Complexity
Let n and m be the sizes of the two arrays. Here is how the two approaches compare.
| Approach | Time | Space |
|---|---|---|
| Combine then sort again | O((n + m) log(n + m)) | O(n + m) |
| Two pointers (merge) | O(n + m) | O(n + m) |
The two-pointer version touches every element exactly once. So the time grows in a straight line with the total number of elements. That is the best you can do here. You have to at least look at each element once to place it.
Tip
When you compare, use a[i] <= b[j] and not just a[i] < b[j]. With <=, equal elements keep their original order. This is called a stable merge. It matters when you sort objects by one field but want to keep the earlier order for ties.
🧩 Key Takeaways
- ✅ Both inputs are already sorted, so never throw that away by sorting again.
- ✅ Use two pointers, one per array, and always take the smaller front element.
- ✅ When one array runs out, copy the rest of the other array straight in.
- ✅ This runs in O(n + m) time, which is the fastest possible here.
- ✅ This is the exact merge step used inside merge sort.
Check Your Knowledge
Test what you learned. Pick an answer for each question, then click Check.
- 1
Why is sorting the combined array again a wasteful approach?
Why: The inputs are already sorted, so paying for a full O((n + m) log(n + m)) sort wastes that free information.
- 2
In the two-pointer merge, which element do you place into the result next?
Why: Because both arrays are sorted, the smallest unused element is always at one of the two pointers, so you take the smaller front element.
- 3
What is the time complexity of the two-pointer merge?
Why: Each element from both arrays is touched exactly once, so the time grows linearly as O(n + m).
- 4
What do you do when one of the arrays runs out before the other?
Why: The leftover elements are already sorted and larger than everything placed so far, so you copy them directly to the end.