Problem
You are given two sorted arrays A and B of lengths m and n, the task is to merge the two sorted arrays in such a way that the merged array is also sorted.
Example
Input
A[] = {3, 9, 10, 18, 23}
B[] = {5, 12, 15, 20, 21, 25}
Output
Merged[] = {3, 5, 9, 10, 12, 15, 18, 20, 21, 23, 25}
Explanation
The merged array is of the size of n + m and contains both the elements of array A and array B in sorted order
Input:
A[] = { 5, 8, 9}
B[] = {4, 7, 8}
Output:
Merged[] = {4, 5, 7, 8, 8, 9}
Explanation
The merged array is of the size of n + m and contains both the elements of array A and array B in sorted order
Index
- Brute Force Approach
- Insertion Sort Approach
- Efficient Approach — Using Merge Sort
Brute Force Approach
The idea is to create a new array C[] of length m+n and put all the elements from A[] and B[] in it and then sort them using Arrays.sort().
Algorithm
- Create an array C of n+m size to store the merged array
- Put the values of both A and B arrays using a for loop
- Sort the C array using Array..sort().
Pseudo Code
Int[] solve(int[] A, int[] B, int n, int m) {
Create a new array C of n+m size
while(i<n) {
C[k++] = A[i++];
}
while(j<m) {
C[k++] = B[j++];
}
Sort C;
return C
}
Output
Array after merging - 1 2 3 4 5 6 7 8
Time Complexity — O((m+n) log(m+n))
We have sorted an array of size m+n using Arrays.sort(), and the time complexity of this operation is O(n log n) which in this case becomes O((m+n )log(m+n))
Space Complexity — O(m+n)
We have created a new array C of size n+m which will store the merged sorted array.
Top comments (2)
Hi there, we encourage authors to share their entire posts here on DEV, rather than mostly pointing to an external link. Doing so helps ensure that readers don’t have to jump around to too many different pages, and it helps focus the conversation right here in the comments section.
If you choose to do so, you also have the option to add a canonical URL directly to your post.
Thanks for the reminder but I kind a not able to do so at the moment because it displays an error message saying 'conical tag has already been taken. Contact yo@dev for further details.'