How to Merge Two Sorted Arrays

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

1. Brute Force Approach
2. Insertion Sort Approach
3. 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

1. Create an array C of n+m size to store the merged array
2. Put the values of both A and B arrays using a for loop
3. 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.

Continue Reading…

Comments

[Sloan the DEV Moderator]

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.

[Ateev Duggal]

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.'