How to Merge Two Sorted Arrays
Merging two sorted arrays is a fundamental problem in Data Structures and Algorithms (DSA).
It is especially important because it introduces the two-pointer technique, which is used in many important algorithms, including the merge step of Merge Sort.
Suppose we have two sorted arrays:
Array 1:
[1, 3, 5, 7]
Array 2:
[2, 4, 6, 8]
We want to merge them into one sorted array:
[1, 2, 3, 4, 5, 6, 7, 8]
The challenge is to do this efficiently without repeatedly sorting the combined array.
Problem Statement
Given two arrays that are already sorted in ascending order, merge them into a single sorted array.
Example
Input:
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
Output:
[1, 2, 3, 4, 5, 6, 7, 8]
Another example:
arr1 = [1, 5, 9]
arr2 = [2, 3, 10]
Output:
[1, 2, 3, 5, 9, 10]
Why Is This Problem Important?
At first, merging two arrays may seem easy.
One simple solution is:
Combine both arrays.
Sort the combined array.
Return the result.
For example:
[1, 3, 5] + [2, 4, 6]
becomes:
[1, 3, 5, 2, 4, 6]
Then sort it:
[1, 2, 3, 4, 5, 6]
However, this ignores an important fact:
Both input arrays are already sorted.
We can use this property to build a more efficient solution.
Approach 1: Combine and Sort
The simplest solution is to concatenate both arrays and sort the result.
Python
def merge_sorted_arrays(arr1, arr2):
result = arr1 + arr2
result.sort()
return result
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
print(merge_sorted_arrays(arr1, arr2))
Output:
[1, 2, 3, 4, 5, 6, 7, 8]
This solution is easy to write, but it is not the most efficient.
Complexity of the Sorting Approach
Suppose the first array contains n elements and the second contains m elements.
The combined array contains:
n + m
elements.
Sorting requires approximately:
O((n + m) log(n + m))
time.
Therefore:
Time Complexity:
O((n + m) log(n + m))
This is more work than necessary because the input arrays are already sorted.
Approach 2: Two-Pointer Technique
The optimal general solution is to use two pointers.
We maintain:
i → position in arr1
j → position in arr2
At each step, compare:
arr1[i]
arr2[j]
Take the smaller value and move that pointer forward.
Example
Consider:
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
Initially:
i = 0
j = 0
Compare:
arr1[i] = 1
arr2[j] = 2
1 is smaller.
Add 1:
result = [1]
Move i:
i = 1
Now compare:
3 and 2
2 is smaller.
result = [1, 2]
Move j.
Continue this process.
Complete Dry Run
Input:
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
arr1 valuearr2 valueSelectedResult121[1]322[1, 2]343[1, 2, 3]544[1, 2, 3, 4]565[1, 2, 3, 4, 5]766[1, 2, 3, 4, 5, 6]787[1, 2, 3, 4, 5, 6, 7]
At this point, arr1 has been completely processed.
The remaining elements of arr2 are:
[8]
Append them:
[1, 2, 3, 4, 5, 6, 7, 8]
Python Two-Pointer Solution
def merge_sorted_arrays(arr1, arr2):
result = []
i = 0
j = 0
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
while i < len(arr1):
result.append(arr1[i])
i += 1
while j < len(arr2):
result.append(arr2[j])
j += 1
return result
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
print(merge_sorted_arrays(arr1, arr2))
Output:
[1, 2, 3, 4, 5, 6, 7, 8]
Understanding the Main Loop
The key part is:
while i < len(arr1) and j < len(arr2):
if arr1[i] <= arr2[j]:
result.append(arr1[i])
i += 1
else:
result.append(arr2[j])
j += 1
Both pointers start at the beginning.
At every step, we select the smaller current value.
Because both arrays are already sorted, the selected value is guaranteed to be the next smallest value in the final array.
Why Can We Ignore the Other Elements?
Suppose:
arr1 = [2, 5, 8]
arr2 = [3, 4, 7]
We compare:
2 and 3
We know 2 must be the smallest remaining value.
Why?
Because:
arr1 = [2, 5, 8]
has no value smaller than 2, and:
arr2 = [3, 4, 7]
also has no value smaller than 3.
Therefore, 2 is safe to add to the result.
This is the key idea behind the two-pointer approach.
Handling Remaining Elements
Eventually, one array may finish before the other.
For example:
arr1 = [1, 2, 3]
arr2 = [4, 5, 6, 7]
After processing:
arr1
the remaining elements are:
[4, 5, 6, 7]
Since arr2 is already sorted, we can directly append the remaining values.
That's why we use:
while i < len(arr1):
result.append(arr1[i])
i += 1
and:
while j < len(arr2):
result.append(arr2[j])
j += 1
Complexity of the Two-Pointer Approach
Suppose:
arr1 contains n elements
arr2 contains m elements
Every element is processed exactly once.
Therefore:
Time Complexity:
O(n + m)
The result array contains n + m elements.
Therefore:
Space Complexity:
O(n + m)
for the output array.
This is optimal for producing a new merged array because the output itself contains n + m elements.
Approach 3: Using Built-In Functions
Many programming languages provide convenient ways to combine arrays.
For example, in Python:
def merge_sorted_arrays(arr1, arr2):
return sorted(arr1 + arr2)
This is very short and readable.
However, from a DSA perspective, it is important to understand the two-pointer technique because it demonstrates how to exploit the fact that the input arrays are already sorted.
Java Solution
import java.util.*;
public class Main {
public static int[] mergeSortedArrays(
int[] arr1,
int[] arr2
) {
int[] result =
new int[arr1.length + arr2.length];
int i = 0;
int j = 0;
int k = 0;
while (
i < arr1.length &&
j < arr2.length
) {
if (arr1[i] <= arr2[j]) {
result[k] = arr1[i];
i++;
} else {
result[k] = arr2[j];
j++;
}
k++;
}
while (i < arr1.length) {
result[k] = arr1[i];
i++;
k++;
}
while (j < arr2.length) {
result[k] = arr2[j];
j++;
k++;
}
return result;
}
public static void main(String[] args) {
int[] arr1 = {
1, 3, 5, 7
};
int[] arr2 = {
2, 4, 6, 8
};
int[] result =
mergeSortedArrays(arr1, arr2);
System.out.println(
Arrays.toString(result)
);
}
}
Output:
[1, 2, 3, 4, 5, 6, 7, 8]
C++ Solution
#include <iostream>
#include <vector>
using namespace std;
vector<int> mergeSortedArrays(
const vector<int>& arr1,
const vector<int>& arr2
) {
vector<int> result;
int i = 0;
int j = 0;
while (
i < arr1.size() &&
j < arr2.size()
) {
if (arr1[i] <= arr2[j]) {
result.push_back(arr1[i]);
i++;
} else {
result.push_back(arr2[j]);
j++;
}
}
while (i < arr1.size()) {
result.push_back(arr1[i]);
i++;
}
while (j < arr2.size()) {
result.push_back(arr2[j]);
j++;
}
return result;
}
int main() {
vector<int> arr1 = {
1, 3, 5, 7
};
vector<int> arr2 = {
2, 4, 6, 8
};
vector<int> result =
mergeSortedArrays(arr1, arr2);
for (int number : result) {
cout << number << " ";
}
return 0;
}
Output:
1 2 3 4 5 6 7 8
JavaScript Solution
function mergeSortedArrays(arr1, arr2) {
const result = [];
let i = 0;
let j = 0;
while (
i < arr1.length &&
j < arr2.length
) {
if (arr1[i] <= arr2[j]) {
result.push(arr1[i]);
i++;
} else {
result.push(arr2[j]);
j++;
}
}
while (i < arr1.length) {
result.push(arr1[i]);
i++;
}
while (j < arr2.length) {
result.push(arr2[j]);
j++;
}
return result;
}
const arr1 = [
1, 3, 5, 7
];
const arr2 = [
2, 4, 6, 8
];
console.log(
mergeSortedArrays(arr1, arr2)
);
Output:
[1, 2, 3, 4, 5, 6, 7, 8]
Handling Duplicate Values
The algorithm also works when both arrays contain duplicate values.
Example:
arr1 = [1, 2, 2, 5]
arr2 = [2, 3, 5, 5]
The merged result is:
[1, 2, 2, 2, 3, 5, 5, 5]
Notice that duplicates are preserved.
This is important because merging arrays and removing duplicates are different problems.
If the question asks to remove duplicates, an additional step or different algorithm is required.
Handling Empty Arrays
The algorithm should also work if one array is empty.
Example:
arr1 = []
arr2 = [1, 2, 3]
Output:
[1, 2, 3]
Another example:
arr1 = [1, 2, 3]
arr2 = []
Output:
[1, 2, 3]
The remaining-elements loops handle these cases automatically.
Handling Negative Numbers
Negative values do not cause any special problems.
Example:
arr1 = [-10, -5, 0]
arr2 = [-8, -3, 2]
Result:
[-10, -8, -5, -3, 0, 2]
The comparison logic works exactly the same way.
Handling Different Array Sizes
The arrays do not need to have the same length.
For example:
arr1 = [1, 4, 7]
arr2 = [2, 3, 5, 6, 8, 9]
Result:
[1, 2, 3, 4, 5, 6, 7, 8, 9]
The two-pointer algorithm works regardless of the sizes of the two arrays.
Important DSA Pattern: Two Pointers
The most important concept in this problem is the two-pointer technique.
We have:
Pointer i → Array 1
Pointer j → Array 2
Then:
Compare arr1[i] and arr2[j]
↓
Take smaller
↓
Move pointer
↓
Repeat
This pattern is useful for many DSA problems involving sorted data.
Common examples include:
Merging sorted arrays
Finding pairs with a target sum
Removing duplicates
Comparing strings
Finding intersections
Merging intervals
Combining sorted linked lists
Merge Sort
Understanding this pattern is extremely valuable for technical interviews.
Merge Two Sorted Arrays Without Sorting
A common interview question is:
Why don't you simply combine both arrays and sort them?
The answer is that sorting wastes the information we already have.
If:
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
we already know that each array is sorted.
Therefore, we can merge them directly in:
O(n + m)
instead of:
O((n + m) log(n + m))
This is a major example of using input properties to improve an algorithm.
Interview Explanation
If an interviewer asks you to merge two sorted arrays, you can explain the solution like this:
Since both arrays are already sorted, I don't need to sort the combined array. I will use two pointers, one for each array. At every step, I compare the elements pointed to by the two pointers and add the smaller one to the result. Then I move the corresponding pointer forward. Once one array is exhausted, I append the remaining elements from the other array. This takes O(n + m) time.
Common Interview Mistakes
Mistake 1: Sorting the Combined Array
This works, but it is less efficient.
result = sorted(arr1 + arr2)
Complexity:
O((n + m) log(n + m))
The two-pointer approach is better.
Mistake 2: Forgetting Remaining Elements
After the main loop:
while i < len(arr1) and j < len(arr2):
one array may still contain elements.
Always process the remaining values.
while i < len(arr1):
result.append(arr1[i])
i += 1
and:
while j < len(arr2):
result.append(arr2[j])
j += 1
Mistake 3: Moving Both Pointers
Suppose:
arr1[i] = 2
arr2[j] = 5
We select 2.
Only pointer i should move.
i++
Pointer j should remain where it is.
Mistake 4: Assuming Both Arrays Have the Same Size
They do not need to have equal lengths.
For example:
[1, 3]
[2, 4, 5, 6, 7]
is completely valid.
Complexity Comparison
ApproachTime ComplexityExtra SpaceCombine + SortO((n + m) log(n + m))O(n + m)Two PointersO(n + m)O(n + m)In-place VariantO(n + m)Depends on constraints
The standard two-pointer solution is the preferred approach when a new merged array is required.
Connection to Merge Sort
This problem is directly related to Merge Sort.
Merge Sort follows these steps:
Unsorted Array
↓
Divide into smaller arrays
↓
Sort smaller arrays
↓
Merge sorted arrays
↓
Final Sorted Array
The merge step uses exactly the same two-pointer idea.
For example:
[1, 4, 7] [2, 3, 8]
↓ ↓
Compare elements
↓
[1, 2, 3, 4, 7, 8]
Understanding how to merge two sorted arrays makes learning Merge Sort much easier.
Practice Examples
Example 1
Input:
[1, 3, 5]
[2, 4, 6]
Output:
[1, 2, 3, 4, 5, 6]
Example 2
Input:
[1, 2, 10]
[3, 4, 5, 6]
Output:
[1, 2, 3, 4, 5, 6, 10]
Example 3
Input:
[-5, -1, 3]
[-4, 0, 2]
Output:
[-5, -4, -1, 0, 2, 3]
Example 4
Input:
[]
[1, 2, 3]
Output:
[1, 2, 3]
Example 5
Input:
[1, 1, 2]
[1, 3, 3]
Output:
[1, 1, 1, 2, 3, 3]
Final Summary
Merging two sorted arrays is an important DSA problem because it teaches the two-pointer technique.
Instead of combining both arrays and sorting them, we can take advantage of their existing sorted order.
The algorithm is:
Start with two pointers
↓
Compare current elements
↓
Take the smaller element
↓
Move that pointer
↓
Repeat
↓
Append remaining elements
The standard solution has:
Time Complexity: O(n + m)
Space Complexity: O(n + m)
where n and m are the sizes of the two input arrays.
The most important lesson is:
When input data is already sorted, look for a way to exploit that ordering instead of sorting it again.
This simple idea leads to efficient algorithms and is one of the most useful patterns to learn in DSA.