## 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 i
^{th}element in array1 is less than j^{th}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**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | import java.util.Arrays; public class MergeSortedArray { public static void main(String[] args) { int[] arr1 = { 1, 18, 22, 100, 105, 1002 }; int[] arr2 = { 16, 17, 19, 21, 1001 }; int[] arr3 = new int[arr1.length + arr2.length]; int i = 0, j = 0, k = 0; while (i < arr1.length && j < arr2.length) { if (arr1[i] < arr2[j]) { arr3[k] = arr1[i]; i++; } else { arr3[k] = arr2[j]; j++; } k++; } // Copy the remaining elements in array 1 to array 3 if (i < arr1.length) { // arraycopy(source, sourcepos, dest, destpos, numOfElements) System.arraycopy(arr1, i, arr3, k, (arr1.length - i)); } // Copy the remaining elements in array 2 to array 3 if (j < arr2.length) { // arraycopy(source, sourcepos, dest, destpos, numOfElements) System.arraycopy(arr2, j, arr3, k, (arr2.length - j)); } System.out.println("Merged Sorted Array" + Arrays.toString(arr3)); } } |

Here is the output of the program.

1 | Merged Sorted Array[1, 16, 17, 18, 19, 21, 22, 100, 105, 1001, 1002] |

## 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**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | import java.util.Arrays; public class MergeSortedArray { public static void main(String[] args) { int[] arr1 = { 1, 18, 22, 100, 105, 1002, -1, -1, -1, -1, -1 }; // -1 to indicate unoccupied space int[] arr2 = { 16, 17, 19, 21, 1001 }; int n = arr2.length; // length of second array int m =(arr1.length-n);//number of elements in first array excluding unoccupied space int k = m + n - 1; while (m > 0 && n > 0) { if (arr1[m - 1] > arr2[n - 1]) { arr1[k--] = arr1[m - 1]; m--; } else { arr1[k--] = arr2[n - 1]; n--; } } /* * 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--; } System.out.println("Merged Sorted Array" + Arrays.toString(arr1)); } } |

Below is the output of the program.

1 | Merged Sorted Array[1, 16, 17, 18, 19, 21, 22, 100, 105, 1001, 1002] |

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.

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

- Introduction to Java Enum data type with example programs - March 31, 2017
- How to send mail using JavaMail API - March 1, 2017
- WatchService in Java with example program - February 27, 2017