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