Merge two sorted arrays

Problem: Given two sorted arrays, the task is to merge them in a sorted manner.

For example:

Input  : arr1[] = { 5, 8, 9}  
         arr2[] = {4, 7, 8}
Output : arr3[] = {4, 5, 7, 8, 8, 9}

As the task is of merging two arrays, we use the idea of Merge Sort.

1. Create an array aux[] of size len1 + len2. 
2. Simultaneously traverse arr1[] and arr2[]. 
1. Pick smaller of current elements in arr1[] and arr2[], copy this smaller element to next position in aux[] and move ahead in aux[] and the array whose element is picked.
3. If there are are remaining elements in arr1[] or arr2[], copy them also in aux[].

import java.util.*;
import java.lang.*;
import java.io.*;
 
class InterviewDesk
{
    /* method to merge two sorted arrays */
    public static void mergeTwoArray(int[] arr1, int[] arr2, int len1, int len2, int[] aux)
    {
        /* iterators of 3 arrays */
        int i = 0, j = 0, k = 0;
     
        /* traversing both arrays */
        while (i < len1 && j <len2)
        {
            /* Check if current element of first array is smaller
               than current element of second array. If yes, store 
               first array element and increment first array index.
               Otherwise do same with second array */
            if (arr1[i] < arr2[j])
                aux[k++] = arr1[i++];
            else
                aux[k++] = arr2[j++];
        }
     
        /* store remaining elements of first array */
        while (i < len1)
            aux[k++] = arr1[i++];
     
        /* store remaining elements of second array */
        while (j < len2)
            aux[k++] = arr2[j++];
    }
     
    public static void main (String[] args) 
    {
        int[] arr1 = {1, 3, 5, 7};
        int len1 = arr1.length;
     
        int[] arr2 = {2, 4, 6, 8};
        int len2 = arr2.length;
     
        int[] aux = new int[len1+len2];
         
        mergeTwoArray(arr1, arr2, len1, len2, aux);
     
        for (int i=0; i < len1+len2; i++)
            System.out.print(aux[i] + " ");
    }
}

Output:

1 2 3 4 5 6 7 8

Time Complexity: O(len1 + len2) and Auxiliary Space: O(len1 + len2)