Merging Two Sorted Arrays in Java
Java Program for Merging Two Sorted Array
In this article, we will dive deep into how to merging two sorted arrays in Java, explore multiple methods, walk through code implementations, analyze the time and space complexities, and explain everything step by step with examples.
Merging two sorted arrays is a classic problem in computer science and is frequently asked in coding interviews.
Merging Two Sorted Arrays In Java Programming
What Does Merge Two Sorted Arrays Mean?
Given two sorted arrays, the goal is to combine them into a single sorted array that maintains the non decreasing order.
- Merging two sorted arrays in Java involves combining two sorted arrays into one sorted array.
- This can be done efficiently by comparing the first element of each array and adding the smaller one to a new array.
- Process is repeated until all elements from both arrays are added to the new array.
Here is an example:
First Array = [12, 18, 40, 60]
Second Array = [47, 56, 89, 90]
Merged Array = [12, 18, 40, 47, 56, 60, 89, 90]
Goal: Merge them into a single sorted array of size n + m.
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Different Approaches for Merging Two Sorted Arrays
Here, we have share 3 approaches for Merging two sorted arrays with Time and Space complexity alongwith Example codes.
- Using Extra Space (Brute Force Method)
- Two Pointers Approach
- In Place Merge Without Extra Space (Advanced)
Method 1: Using Extra Spaces for Merging two sorted array
Algorithm:
- Create a result array of size n + m.
- Use two pointers i and j to iterate over arr1 and arr2.
- Compare arr1[i] and arr2[j]:
Add the smaller element to the result array.
Move the pointer of the array from which the element was taken.
Copy remaining elements (if any).
Return the result array.
Space Complexity: O(n + m): Because of extra result array
Code:
public class MergeSortedArrays {
public static int[] mergeArrays(int[] arr1, int[] arr2) {
int n = arr1.length, m = arr2.length;
int[] result = new int[n + m];
int i = 0, j = 0, k = 0;
while(i < n && j < m) {
if(arr1[i] <= arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
while(i < n) {
result[k++] = arr1[i++];
}
while(j < m) {
result[k++] = arr2[j++];
}
return result;
}
public static void main(String[] args) {
int[] arr1 = {1, 3, 5, 7};
int[] arr2 = {2, 4, 6, 8};
int[] merged = mergeArrays(arr1, arr2);
System.out.print("Merged Array: ");
for(int num : merged) {
System.out.print(num + " ");
}
}
}
Output:
Merged Array: 1 2 3 4 5 6 7 8
Method 2: Using Two Pointers for Merging two sorted array
Algorithm:
- Initialize two pointers:
i = 0 to traverse the first array (arr1)
j = 0 to traverse the second array (arr2)
While both i < arr1.length and j < arr2.length:
Compare arr1[i] and arr2[j].
If arr1[i] <= arr2[j], print arr1[i] and increment i.
Else, print arr2[j] and increment j.
After the loop ends, one of the arrays may still have elements left:
Print the remaining elements in arr1 (from i to end)
Print the remaining elements in arr2 (from j to end)
The merged elements will be printed in sorted order without using any extra array.
Space Complexity: O(1): no extra space used.
Code:
public class MergePrint {
public static void mergeAndPrint(int[] arr1, int[] arr2) {
int i = 0, j = 0;
while(i < arr1.length && j < arr2.length) {
if(arr1[i] <= arr2[j]) {
System.out.print(arr1[i++] + " ");
} else {
System.out.print(arr2[j++] + " ");
}
}
while(i < arr1.length) {
System.out.print(arr1[i++] + " ");
}
while(j < arr2.length) {
System.out.print(arr2[j++] + " ");
}
}
public static void main(String[] args) {
int[] arr1 = {10, 20, 30};
int[] arr2 = {5, 15, 25, 35};
System.out.print("Merged Output: ");
mergeAndPrint(arr1, arr2);
}
}
Output:
Merged Output: 5 10 15 20 25 30 35
Method 3: Using In Place Merge (Without Extra Array) - Advanced Method
This method is only possible when one of the arrays has extra space (like a buffer at the end), or you’re dealing with data structures like ArrayList.
Otherwise, Java arrays are fixed size.
Let’s assume arr1 has size n + m, where the last m elements are empty (0), and arr2 has m elements.
Algorithm:
- Start from the end of both arrays.
- Fill from the end of arr1.
- Place the largest element at the last position, then move backward.
Code:
public class InPlaceMerge {
public static void merge(int[] arr1, int n, int[] arr2, int m) {
int i = n - 1;
int j = m - 1;
int k = n + m - 1;
while(i >= 0 && j >= 0) {
if(arr1[i] > arr2[j]) {
arr1[k--] = arr1[i--];
} else {
arr1[k--] = arr2[j--];
}
}
while(j >= 0) {
arr1[k--] = arr2[j--];
}
}
public static void main(String[] args) {
int[] arr1 = new int[10];
arr1[0] = 1; arr1[1] = 3; arr1[2] = 5; arr1[3] = 7;
int n = 4;
int[] arr2 = {2, 4, 6, 8};
int m = 4;
merge(arr1, n, arr2, m);
System.out.print("In-place Merged Array: ");
for(int i = 0; i < n + m; i++) {
System.out.print(arr1[i] + " ");
}
}
}
Output:
In-place Merged Array: 1 2 3 4 5 6 7 8
Space Complexity: O(1)
Edge Cases to Consider for Merging Sorted Arrays
- One array is empty:
arr1 = {}, arr2 = {1,2,3} → Output: {1,2,3} - Arrays contain duplicates:
arr1 = {1,2,2}, arr2 = {2,3} → Output: {1,2,2,2,3} - Arrays already merged:
arr1 = {1,2}, arr2 = {3,4} → Output: {1,2,3,4}
Difference between methods for merging sorted array
| Method for Merging | Extra Space used | Time Complexity | Space Complexity | Conclusion |
|---|---|---|---|---|
| Brute Force (New Array) | Yes | O(n + m) | O(n + m) | Simple and safe |
| Two Pointers (Print Only) | No | O(n + m) | O(1) | Efficient if no storage needed |
| In-Place Merge | No (if buffer exists) | O(n + m) | O(1) | Efficient but needs buffer space |
Conclusion
Merging two sorted arrays is a fundamental problem that enhances your understanding of array traversal, pointer logic, and space optimization.
We explored three methods:
- Beginner friendly: using extra space.
- Optimized: two pointer without extra storage.
- Advanced: in place merging.
Each approach has its use case depending on the requirements of space, efficiency, and real time application.
FAQ's related to Merging Sorted Arrays
Answer:
Fastest way to merge them is by using the Two-Pointer Technique: similar to the merge step in Merge Sort.
Answer:
This is a trick question because all sorting involves some kind of sorting logic, even if you’re not explicitly calling Arrays.sort() or Collections.sort().
Answer:
Java 8 introduced the Stream API, which allows a functional, declarative approach to processing data. You can merge two unsorted arrays and sort them using Stream.concat() and sorted().
Answer:
In place Merge Sort using a single array (without a second helper array) is challenging, because the merge step usually needs extra space.
However, a workaround is possible by:
- Recursively dividing the array.
- Merging sorted halves manually, without using extra space (at the cost of more complex code and higher runtime constants).
But for clarity and practicality, we typically use a temporary array during the merge step.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment