Merge Two Sorted Arrays
Java coding interview problem for Array Logic: Merge Two Sorted Arrays.
Merging two sorted arrays is one of the most fundamental array problems in programming interviews.
This problem teaches the foundation of the merge operation, which is heavily used in:
- Merge Sort
- Database joins
- Data synchronization
- External sorting
- Log processing systems
It tests important concepts:
- Array traversal
- Two Pointer technique
- Sorting
- Space optimization
- In-place algorithms
What is Merging Two Sorted Arrays?
Given two sorted arrays, combine them into a single sorted array.
The final array should contain:
- All elements from first array
- All elements from second array
- Elements arranged in sorted order
Example 1
Input:
Array 1:
[1,3,5]
Array 2:
[2,4,6]
Output:
[1,2,3,4,5,6]
Example 2
Input:
Array 1:
[2,3,8]
Array 2:
[1,4,7,9]
Output:
[1,2,3,4,7,8,9]
Why is This Question Asked in Interviews?
Interviewers ask this problem because it evaluates:
- Understanding of sorted data
- Pointer manipulation
- Time complexity optimization
- Memory management
It is a core concept behind:
- Merge Sort
- K-way merge
- Priority Queue problems
- Database merge operations
Real-World Applications
Database Merge Operations
Suppose two systems maintain sorted customer IDs.
System A:
[1001,1003,1005]
System B:
[1002,1004,1006]
Merged result:
[1001,1002,1003,1004,1005,1006]
Log Processing
Two servers generate timestamp-sorted logs.
Server 1:
10:01
10:03
10:05
Server 2:
10:02
10:04
10:06
Merge:
10:01
10:02
10:03
10:04
10:05
10:06
Data Synchronization
Combining sorted datasets from multiple sources.
Merge Sort Algorithm
The merge step combines two sorted halves:
Left Sorted Array
+
Right Sorted Array
↓
Sorted Result
Problem Statement
Given two sorted integer arrays:
nums1
nums2
merge them into one sorted array.
Constraints
Example:
1 <= nums1.length, nums2.length <= 100000
Rules:
- Both arrays are already sorted.
- Output should remain sorted.
- Duplicate values are allowed.
Understanding Merge Logic
Consider:
Array 1:
[1,3,5]
Array 2:
[2,4,6]
Compare first elements:
1 vs 2
Choose:
1
Compare:
3 vs 2
Choose:
2
Compare:
3 vs 4
Choose:
3
Continue until all elements are merged.
Array Visualization
Input:
Array 1
1 3 5
↑
Array 2
2 4 6
↑
Compare:
1 < 2
Take:
1
Move pointer.
Result:
[1]
Continue:
[1,2,3,4,5,6]
Dry Run
Input:
nums1:
[1,3,5]
nums2:
[2,4,6]
Initialize:
i = 0
j = 0
Result:
[]
Compare:
nums1[i] = 1
nums2[j] = 2
Take:
1
Result:
[1]
Compare:
3 vs 2
Take:
2
Result:
[1,2]
Compare:
3 vs 4
Take:
3
Result:
[1,2,3]
Continue:
Final:
[1,2,3,4,5,6]
Approach 1 — Brute Force Using Combined Array
The simplest solution:
- Create a new array.
- Copy both arrays.
- Sort the combined array.
Algorithm
- Create result array of size:
n + m
- Copy elements from first array.
- Copy elements from second array.
- Sort result.
- Return.
Java Program
import java.util.Arrays;
public class MergeSortedArraysBruteForce {
public static int[] merge(
int[] nums1,
int[] nums2) {
int[] result =
new int[nums1.length +
nums2.length];
int index = 0;
for (int number : nums1) {
result[index++] = number;
}
for (int number : nums2) {
result[index++] = number;
}
Arrays.sort(result);
return result;
}
public static void main(String[] args) {
int[] nums1 =
{1,3,5};
int[] nums2 =
{2,4,6};
System.out.println(
Arrays.toString(
merge(nums1, nums2)));
}
}
Output
[1,2,3,4,5,6]
Step-by-Step Explanation
Input:
nums1:
[1,3,5]
nums2:
[2,4,6]
Combine:
[1,3,5,2,4,6]
Sort:
[1,2,3,4,5,6]
Complexity Analysis
Copying:
O(n+m)
Sorting:
O((n+m)log(n+m))
Overall:
O((n+m)log(n+m))
Space:
O(n+m)
Advantages
- Very easy.
- Beginner friendly.
- Works for any arrays.
Drawbacks
- Ignores the fact that arrays are already sorted.
- Sorting adds unnecessary work.
- Uses extra memory.
Approach 2 — Sorting After Merge
This approach is similar but separates the merge and sort steps.
Steps:
- Add all elements into List.
- Sort the list.
- Convert back to array.
Java Program
import java.util.*;
public class MergeSortedArraysSorting {
public static int[] merge(
int[] nums1,
int[] nums2) {
List<Integer> list =
new ArrayList<>();
for (int n : nums1) {
list.add(n);
}
for (int n : nums2) {
list.add(n);
}
Collections.sort(list);
return list.stream()
.mapToInt(Integer::intValue)
.toArray();
}
}
Complexity Analysis
Time:
O((n+m)log(n+m))
Space:
O(n+m)
Advantages
- Simple Java implementation.
- Uses Collections API.
- Easy readability.
Drawbacks
- Extra boxing overhead.
- Sorting is unnecessary.
- Not optimal.
Approach 3 — Two Pointer Approach (Optimal)
Because both arrays are already sorted,
we can merge them in one pass.
This is the approach used internally in:
- Merge Sort
- Database merge operations
Two Pointer Concept
Use two pointers:
i → nums1 pointer
j → nums2 pointer
Compare:
nums1[i]
and
nums2[j]
Pick smaller element.
Example
nums1:
[1,3,5]
i
nums2:
[2,4,6]
j
Compare:
1 < 2
Take:
1
Move:
i++
Algorithm
- Create result array.
- Initialize:
i = 0
j = 0
- Compare elements.
- Add smaller value.
- Move corresponding pointer.
- Add remaining elements.
Java Program
import java.util.Arrays;
public class MergeSortedArraysTwoPointer {
public static int[] merge(
int[] nums1,
int[] nums2) {
int[] result =
new int[nums1.length +
nums2.length];
int i = 0;
int j = 0;
int k = 0;
while (i < nums1.length &&
j < nums2.length) {
if (nums1[i] <= nums2[j]) {
result[k++] =
nums1[i++];
} else {
result[k++] =
nums2[j++];
}
}
while (i < nums1.length) {
result[k++] =
nums1[i++];
}
while (j < nums2.length) {
result[k++] =
nums2[j++];
}
return result;
}
public static void main(String[] args) {
int[] nums1 =
{1,3,5};
int[] nums2 =
{2,4,6};
System.out.println(
Arrays.toString(
merge(nums1, nums2)));
}
}
Output
[1,2,3,4,5,6]
Step-by-Step Explanation
Input:
nums1 = [1,3,5]
nums2 = [2,4,6]
Pointers:
i = 0
j = 0
Compare:
1 and 2
Take:
1
Compare:
3 and 2
Take:
2
Compare:
3 and 4
Take:
3
Continue:
Result:
[1,2,3,4,5,6]
Complexity Analysis
Time:
O(n+m)
Space:
O(n+m)
Advantages
- Optimal time complexity.
- Uses sorted property.
- Simple and efficient.
- Interview recommended.
Drawbacks
- Requires extra result array.
Approach 4 — In-Place Merge Approach
The two pointer approach creates a new array.
But some interview problems ask:
Merge two sorted arrays without using extra space.
For this requirement, we modify the arrays directly.
Problem Variant
Given:
nums1 = [1,3,5,0,0,0]
nums2 = [2,4,6]
Here:
nums1has enough empty space.- First three positions contain valid elements.
- Remaining positions are reserved.
Expected Output
[1,2,3,4,5,6]
Reverse Two Pointer Technique
Instead of merging from the beginning,
we merge from the end.
Why?
Because empty spaces are available at the end of nums1.
Pointer Setup
Use three pointers:
i = last valid element in nums1
j = last element in nums2
k = last position in nums1
Example:
nums1:
[1,3,5,0,0,0]
i k
nums2:
[2,4,6]
j
Algorithm
- Start from the end of both arrays.
- Compare largest elements.
- Place larger element at the end.
- Move pointers backward.
- Continue until nums2 is processed.
Java Program
import java.util.Arrays;
public class MergeSortedArraysInPlace {
public static void merge(
int[] nums1,
int m,
int[] nums2,
int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (i >= 0 &&
j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k--] =
nums1[i--];
} else {
nums1[k--] =
nums2[j--];
}
}
while (j >= 0) {
nums1[k--] =
nums2[j--];
}
}
public static void main(String[] args) {
int[] nums1 =
{1,3,5,0,0,0};
int[] nums2 =
{2,4,6};
merge(nums1,3,nums2,3);
System.out.println(
Arrays.toString(nums1));
}
}
Output
[1,2,3,4,5,6]
Step-by-Step Explanation
Input:
nums1:
[1,3,5,0,0,0]
nums2:
[2,4,6]
Pointers:
i = 2
j = 2
k = 5
Compare:
5 and 6
6 is larger.
Place:
nums1[5] = 6
Array:
[1,3,5,0,0,6]
Compare:
5 and 4
5 is larger.
Place:
nums1[4] = 5
Array:
[1,3,5,0,5,6]
Compare:
3 and 4
Place:
4
Array:
[1,3,5,4,5,6]
Continue:
Final:
[1,2,3,4,5,6]
Complexity Analysis
Time:
O(n + m)
Space:
O(1)
Advantages
- Optimal memory usage.
- True in-place merge.
- Common interview problem.
- Used in production systems.
Drawbacks
- Requires extra space in first array.
- Slightly harder pointer logic.
Approach 5 — Using Java Streams
Java Streams can merge arrays in a functional style.
The approach:
- Convert arrays into streams.
- Concatenate streams.
- Sort values.
- Convert back to array.
Java Program
import java.util.Arrays;
import java.util.stream.IntStream;
public class MergeSortedArraysStreams {
public static int[] merge(
int[] nums1,
int[] nums2) {
return IntStream.concat(
Arrays.stream(nums1),
Arrays.stream(nums2))
.sorted()
.toArray();
}
public static void main(String[] args) {
int[] nums1 =
{1,3,5};
int[] nums2 =
{2,4,6};
System.out.println(
Arrays.toString(
merge(nums1, nums2)));
}
}
Output
[1,2,3,4,5,6]
Step-by-Step Explanation
Streams:
nums1
[1,3,5]
and:
nums2
[2,4,6]
are combined:
[1,3,5,2,4,6]
Apply:
sorted()
Result:
[1,2,3,4,5,6]
Complexity Analysis
Time:
O((n+m) log(n+m))
Space:
O(n+m)
Advantages
- Short code.
- Easy functional style.
- Good for data processing pipelines.
Drawbacks
- Ignores sorted property.
- Uses extra memory.
- Sorting adds overhead.
Approach 6 — Using Collections
Java Collections provide another simple approach.
The idea:
- Add both arrays into a List.
- Sort the List.
- Convert back.
Java Program
import java.util.*;
public class MergeSortedArraysCollections {
public static List<Integer> merge(
int[] nums1,
int[] nums2) {
List<Integer> result =
new ArrayList<>();
for (int value : nums1) {
result.add(value);
}
for (int value : nums2) {
result.add(value);
}
Collections.sort(result);
return result;
}
public static void main(String[] args) {
int[] nums1 =
{1,3,5};
int[] nums2 =
{2,4,6};
System.out.println(
merge(nums1, nums2));
}
}
Output
[1,2,3,4,5,6]
Complexity Analysis
Time:
O((n+m) log(n+m))
Space:
O(n+m)
Advantages
- Simple Java code.
- Easy readability.
- Useful for application development.
Drawbacks
- Integer boxing overhead.
- Not optimal for algorithms.
- Uses extra memory.
Handling Duplicate Values
Merging should preserve duplicates.
Example:
Input:
nums1:
[1,2,2]
nums2:
[2,3,3]
Output:
[1,2,2,2,3,3]
Why Keep Duplicates?
Merge operation combines datasets.
It does not remove values.
For duplicate removal, use:
- Set
- HashSet
- Distinct operation
Merge vs Union
Many candidates confuse these.
Merge
Keeps duplicates.
Example:
[1,2]
+
[2,3]
=
[1,2,2,3]
Union
Removes duplicates.
Example:
[1,2]
+
[2,3]
=
[1,2,3]
Primitive vs Object Arrays
Primitive Array
Example:
int[]
Advantages:
- Better performance.
- Less memory.
- No boxing.
Recommended for:
- Large numerical datasets.
- Competitive programming.
Object Array
Example:
Integer[]
Advantages:
- Works with Collections.
- Supports generics.
- Easier integration.
Comparison of All Approaches
| Approach | Time Complexity | Space Complexity | Recommended |
|---|---|---|---|
| Combine + Sort | O((n+m)log(n+m)) | O(n+m) | Beginner |
| Collections Sort | O((n+m)log(n+m)) | O(n+m) | Application code |
| Two Pointer | O(n+m) | O(n+m) | Interview |
| In-Place Merge | O(n+m) | O(1) | Advanced Interview |
| Streams | O((n+m)log(n+m)) | O(n+m) | Functional Style |
Common Interview Mistakes
Mistake 1
Sorting already sorted arrays.
Example:
Arrays.sort(nums1);
This wastes time.
Mistake 2
Using forward merging for in-place problems.
Problem:
You overwrite useful values.
Mistake 3
Forgetting remaining elements.
Example:
nums1:
[1,2,8]
nums2:
[3,4,5,6]
After main loop, copy remaining values.
Mistake 4
Removing duplicates accidentally.
Merge is not union.
Mistake 5
Ignoring empty arrays.
Examples:
[]
[1,2,3]
Should return:
[1,2,3]
Edge Cases
| Input | Output |
|---|---|
[],[] |
[] |
[],[1,2] |
[1,2] |
[1],[2] |
[1,2] |
| Duplicate values | Preserve duplicates |
| Negative numbers | Works |
Interview Follow-up Questions
Q1. Merge two arrays without extra space.
Q2. Merge K sorted arrays.
Q3. Merge intervals.
Q4. Merge two linked lists.
Q5. Remove duplicates while merging.
Q6. Find median of two sorted arrays.
Q7. Implement merge sort.
Q8. Merge arrays in descending order.
Related Problems
- Merge Sort
- Merge Intervals
- Merge K Sorted Arrays
- Median of Two Sorted Arrays
- Intersection of Arrays
- Union of Arrays
- Two Pointer Problems
Key Takeaways
- Two sorted arrays can be merged efficiently using two pointers.
- The optimal approach:
Two Pointer Merge
Complexity:
Time: O(n+m)
- In-place merge provides:
Space: O(1)
- Always consider whether:
- Duplicates should remain.
- Extra space is allowed.
- Arrays are already sorted.
Frequently Asked Interview Questions
Q1. What is the optimal merge approach?
Two pointer technique.
Time: O(n+m)
Q2. Why don't we sort again?
Because input arrays are already sorted.
Q3. How do you merge without extra space?
Use reverse two pointers.
Q4. What is the difference between merge and union?
Merge:
Keeps duplicates
Union:
Removes duplicates
Q5. Where is merge algorithm used?
Examples:
- Merge Sort
- Database joins
- External sorting
- Data pipelines
Interview Tip
When asked:
"Merge two sorted arrays."
Explain the progression:
- Combine and sort → O((n+m)log(n+m))
- Two pointers → O(n+m)
- Reverse pointers for in-place merge → O(1) space
The ability to identify and use the sorted property demonstrates strong understanding of Java arrays, algorithms, and optimization techniques.