# Write a Java program to merge two sorted arrays

## Java program to merge two sorted arrays

Write a Java program to merge two sorted arrays is one of the frequently asked Java coding interview questions. In this article we will see the solution for the same.

There can be two versions of the program.

• Merging two sorted array into a third array. This problem should be solved with time complexity of O(n) as well as the space complexity of O(n), where n is the total number of elements.
• There are two sorted arrays. First array is of size m+n containing m elements. Second array is of size n and contains n elements. These two arrays should be merged into the first array(size m+n) such that the output is sorted. In this case the space complexity should be O(1).

Let us see the Java program for both the cases.

## Java code to merge two sorted arrays into third array

Algorithm

• Compare the elements in array1 with elements in array2 (one by one), if the ith element in array1 is less than jth element in array2 then store arr1[i] into new array and increase the index i else store arr2[j] into new array and increase the index j.
• Once any one of the array is traversed fully, stop the comparison and copy the remaining elements of array1 or array2 into the new array.

Below is a pictorial representation of the algorithm.

Here is the Java program.

MergeSortedArray.java

Here is the output of the program.

## Java code to merge two sorted arrays into the first array

Algorithm

• In this problem, the approach is to compare the elements in array 1 and array 2 backwards.
• Since both the arrays are already sorted, while comparing backwards, if the last element in array 1 is greater than the last element in array 2, then it should be the highest element in the resultant array. So it should be moved to the end of resultant array.
• On the other hand, if the last element in array 2 is greater than the last element in array 1, then it should be the highest element in the resultant array. So it should be moved to the end of resultant array.
• In a similar way the elements in other position should be compared from backwards and it should be moved to position backwards from end.

Here is the Java program.

MergeSortedArray.java

Below is the output of the program.

Hope you have learnt Java program to merge two sorted arrays. If you have any doubts, post it in the comments section.

The following two tabs change content below.

#### Uday

Working as a Java developer since 2010. Passionate about programming in Java. I am a part time blogger.

#### Latest posts by Uday (see all)

One comment
1. /*
* Copy the remaining elements that are not copied from array 2 to
* array 1. This happens after all the elements in array 1 is compared
* with array2 and still some elements are not placed into array 1 from array 2
*/
while (n > 0) {
arr1[k–] = arr2[n – 1];
n–;
}

if array1 is always going to be bigger than array2 since we are merging array2 into array1. I doubt that we will ever come to this scenario of array2 items left over after comparing all the int in array1 with array2.