An array is one of the most important and basic data structures that a programmer has to work on. As a result of its significant usage, questions related to arrays are generally asked in interviews.
Therefore, no matter to which company you are going for an interview, never miss out on important topics like strings and arrays. However, revising and remembering each concept is not easy and possible.
This is why you must always prepare some of the most-asked questions related to the topic. One question which has been asked a lot of time in interviews is about merging two sorted arrays. In case you are not familiar with this coding problem, we have got you covered.
Check out all the possible methods to merge two sorted arrays. However, let’s begin with understanding what the problem is.
The Problem Statement
You will be provided with two sorted arrays. Here, you will have to merge these two arrays in ascending order.
To understand better, consider the following example:
You are given two arrays A={ 1, 2, 4, 5, 7, 8} and B= { 3, 6, 9, 10}
The output of the program should be C={ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Methods To Merge Two Sorted Arrays
Merging two sorted arrays can be done using the following three methods.
- Naive method
- Insert and Sort method
- Merge Sort method
- Two pointers approach
Let’s begin with understanding each of these methods in detail.
Naive Method
As the name suggests, this is the very basic approach used for merging two sorted arrays. The method follows the following simple steps:
- To begin with, you need to take all the elements present in array 1 and array 2.
- Add these elements to array 3
- When done, you will have to sort array 3.
Complexity Analysis
- Time Complexity: The time complexity of this method is calculated as O(m+n) log(m+n). This is because the size of the third array will be m+n.
- Space complexity: Since we are using no extra space to carry out this process, the space complexity is calculated as O(1).
Insert and sort method
Another method that you can use for merging two sorted arrays is insert and sort array. In this method, the following steps are followed:
- To begin with, initialise and declare an array Ar2 having size n1+n2.
- Now, you will have to copy all the elements of A1 to Ar3.
- You will have to then traverse the Ar2 and start inserting elements one by one of Ar3 to Ar1.
Complexity Analysis
- Time Complexity: the time complexity of this method is calculated as O(n1 *n2).
- Space complexity: the space complexity of this method is calculated as O(n1 +n2) since we are using extra space.
Merge Sort Method
Now that we are aware that both arrays are sorted, we are going to make full use of it. We will apply a method similar to that of merge sort for merging two sorted arrays. To use this method, you need to follow the below-mentioned steps.
- To begin with, you will have to create additional space of size n+m.
- You will then have to use two pointers j and i and initialize them at 0.
- Now, the pointer i will point towards the first array and j will point towards the second array.
- You will have to traverse these arrays simultaneously and then choose the smallest element present among all the elements of both arrays.
- You will have to insert that element into the additional space you have created.
- Now, simply keep on incrementing the pointers and perform the whole process till the arrays are merged.
- In the end, you will have to return the final merged array.
Complexity Analysis
- Time Complexity: The time complexity of this method is calculated as O(n+m).
- Space Complexity: The space complexity of this method is calculated as O(n+m) because of the additional space being used.
Two-pointers approach
Two pointers approach is one of the easiest and most effective methods to work with sorted arrays. However, for merging two sorted arrays using a two pointers approach, you need to have a good understanding of arrays and how the technique works.
To perform the two-pointers approach, you need to follow the below-mentioned steps:
- To begin with, you will have to initialize the length of the given arrays as m and n.
- Now, create an additional array of size m+n.
- You will then have to initialize the loops i, k, and j at index 0 for all three arrays.
- Start comparing A[i] and B[j] in case i<m and j>n.
- In case A[i] is less than B[j], you will have to copy A[i] into the C array. Also, increment the value of k and i.
- Otherwise, you will have to copy B[j] into C[k]. Also, implement k and j.
- Also, if i<m, you will have to copy A[i] into C[k]. increment k and i.
- Similarly, if j<n, you will have to copy B[j] into C[k]. Increment k and j.
- You need to follow the same set of steps until both arrays A and B are empty.
Complexity Analysis
- Time Complexity: The time complexity of this method is calculated as O(m+n).
- Space Complexity: The space complexity of this method is calculated as O(1) because we are not using any extra space.
Conclusion
You are most likely to find the question to merge two sorted arrays along with questions like the longest common prefix, rotation of an array, or binary search. You can use four methods to merge the given sorted arrays.
Each method has its own time and space complexity and this is why you need to analyse the space and time usage before you choose a method for merging two sorted arrays. Make sure to choose the method which seems most optimal to you.
