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.

merge sorted array java

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.
Working as a Java developer since 2010. Passionate about programming in Java. I am a part time blogger.

Add Comment

Required fields are marked *. Your email address will not be published.