Java code to merge two sorted arrays into third array with example

In core java interview, most of the companies ask the candidate to write program to test their logical ability, practical knowledge & experience in java language. Merging of two sorted arrays is one of the  java program which is frequently asked in Java interview. The following question or similar questions may be asked.

arr1 and arr2 are two sorted arrays. Merge the arrays arr1 & arr2 in a result array (i.e. Union of arr1 & arr2). The result array should also be in sorted order. Create a function called merge which accepts arr1 and arr2 and returns the result array.

e.g. arr1={4,6, 9, 20, 56} , arr2={1, 7, 25, 45, 70}

result = {1,4,6,7, 9,20, 25, 45, 56, 70}

The following code merges the two arrays into third array in a sorted order.

Steps to  merge two sorted arrays

1. If the first array is empty (i.e a1.length <=0 ), then copy the elements of the array arr2 to the result array. return the result

2. If the second array is empty ( i.e arr2.length <=0), then copy all the elements of the array arr1 to the result array. return the result

3. Compare the element in the arr1 with element in the arr2 and copy the small element to result ie. if the arr1[i]<arr2[j], copy arr1[i] to result, and increase i , otherwise copy arr2[j] to result, and increase j

4. Copy the remaining elements either in arr1 OR in arr2 to result, return the result


package com.javaonline;

class Merge2SortedArrays
{
public static void main(String[] args) {
int arr1[]={4,6, 9, 20, 56};
int arr2[]={1, 7, 25, 45, 70};
int[] result=merge(arr1, arr2);
for (int j=0; j<result.length;j++)
System.out.print(result[j]+ " ");
}

static int[] merge(int[] arr1, int[] arr2)
{
int arr1_Length=arr1.length;
int arr2_Length=arr2.length;
int[] result = new int[arr1_Length + arr2_Length];
int i=0, j = 0;

for(int k = 0 ; k< (arr1_Length + arr2_Length);k++)
{
//If arr1 is empty, copy the elements of the array arr2 to the result array .
//When i equals the length of array arr1 , copy the remaining elements in the array arr2 to result
if ( i >= arr1_Length ) //for step1 & 4
{
result[k] = arr2[j];
j ++;
}
//If arr2 is empty, copy the elements of the array arr1 to the result array .
//When j equals the length of array arr2 , copy the remaining elements in the array arr1 to result
else if ( j >= arr2_Length) // For step 2 &amp; 4
{
result[k] = arr1[i];
i ++;
}
else
{

if ( arr1[i] < arr2[j]) // step 3
{
result[k] = arr1[i];
i ++;
}
else
{
result[k] = arr2[j];
j ++;
}
}
}
return result;
}
}

Output:

1 4 6 7 9 20 25 45 56 70

Time complexity of above program is O(n) and space complexity O(1)

Merging of two arrays can be done using the following code that uses built-in System.arraycopy method which is faster than using a loop for copying arrays. The resulting array is not sorted.

int arr1[]={3,10,30, 36,5};
int arr2[]={7,4,6,55,43,33,22,90, 3};
int result[]=new int[arr1.length+arr2.length];
System.arraycopy(arr1, 0, result,0,arr1.length);
System.arraycopy(arr2, 0, result,arr1.length, arr2.length); // 0 is starting position of arr2 and arr1.length is the starting position in the result. arr2.length is the number of elements to be copied.</p>

3 10 30 36 5 7 4 6 55 43 33 22 90 3

To sort any array, you can use, Arrays.sort(array);

You may also like

Leave a Reply