Question

Algorithm to merge two sorted array into a single sorted array​

Answer 1

1. Create an array arr3[] of size n1 + n2.
2. Copy all n1 elements of arr1[] to arr3[]
3. Traverse arr2[] and one by one insert elements (like insertion sort) of arr3[] to arr1[]. This step take O(n1 * n2) time.

Answer 2

Answer:

import java.util.*;

public class Main

{

   static void merge(int[] arr , int[] a , int[] b){

       java.util.Arrays.sort(a); // sorting a in case it is not sorted

       java.util.Arrays.sort(b); // sorting b in case it is not sorted

       int ls = a.length;

       int rs = b.length;

       int i = 0 , j = 0 , k = 0;

           while(i < ls && j < rs){

               if(a[i] <= b[j]){

                   arr[k] = a[i];

                   i++;

               }

               else{

                   arr[k] = b[j];

                   j++;

               }

               k++;

           }

           while(i < ls){

               arr[k] = a[i];

               i++;

               k++;

           }

           while(j < rs){

               arr[k] = b[j];

               j++;

               k++;

           }

   }

public static void main(String[] args) {

 int[] left = {5,1,2,3,6};

 int[] right = {8,4,5,9,2};

 int[] arr = new int[10];

 merge(arr,left,right);

 System.out.println("First array: " + Arrays.toString(left));

 System.out.println("Second array: " + Arrays.toString(right));

 System.out.println("After merging 2 arrays and merging it into 1 array: " + Arrays.toString(arr));

}

}

Explanation: