Arrays: Program to merge two sorted arrays


The key idea to note here is that both the arrays are sorted. Therefore, taking advantage of this fact we can compare the elements in sequence of both the arrays and try to create a merged array with right elements in place

 
Approach
  1. Create a new array called 'array3' of size that is equal to the addition of the size of both sorted arrays (n1 and n2 are the size of the two sorted arrays the size of the new array will be n1 + n2)
  2. Simultaneously traverse array1 and array2
  3. Compare the first elements of both the array and store the smaller element in array3
  4. Move the pointer ahead of array3 and the array from which element is picked. Then perform the comparison again
  5. Perform the above step untill the loop ends
  6. Lastly if there are remaining elements in array1 and array2 then also copy them in array3
 
Complexity

Time Complexity : O(n1 + n2) , where n1 & n2 is the number of elements in array1 & array2
Space Complexity: O(n1 + n2) , where n1 & n2 is the number of elements in array1 & array2

 

Java Code
import java.util.*;

    class MergeTwoSortedArrays{
    
        private int[] mergeSortedArrays(int[] array1, int[] array2){
            
            int n1 = array1.length;
            int n2 = array2.length;
    
            int[] array3 = new int[n1 + n2];
    
            int i = 0, j = 0, k = 0;
    
            while (i < n1 && j < n2){
                if (array1[i] < array2[j])
                    array3[k++] = array1[i++];
                else
                    array3[k++] = array2[j++];
            }
    
            while (i < n1) // Store remaining elements of 1st array
                array3[k++] = array1[i++];
    
            while (j < n2) // Store remaining elements of 2nd array
                array3[k++] = array2[j++];
    
            return array3;
    
        }
        
        public static void main (String[] args)
        {
            int[] array1 = {10, 30, 50, 70};
        
            int[] array2 = {20, 40, 60, 80};
            System.out.println("Array 1 : " + Arrays.toString(array1));
            System.out.println("Array 2 : " + Arrays.toString(array2));
    
            MergeTwoSortedArrays mt = new MergeTwoSortedArrays();
        
            int[] mergedArray = mt.mergeSortedArrays(array1, array2);
            System.out.print("Arrays after merging: ");
    
            for (int i=0; i < mergedArray.length; i++)
                System.out.print(mergedArray[i] + " ");
        }
    
    }   
 
Output

Array 1 : [10, 30, 50, 70]
Array 2 : [20, 40, 60, 80]
Arrays after merging: 10 20 30 40 50 60 70 80



Thanks for feedback.



Read More....
Check if an array is a min heap
Convert a sorted array into a binary search tree - recursive approach
Print the elements of an array
Find the kth largest element in the array
Find the kth smallest element in the array