How to Merge Two Sorted Arrays

In this example, we’ll see how to merge two sorted arrays:

Input:
int[] arr1 = { 10, 20, 30 };
int[] arr2 = { 1, 5, 8, 12, 18 };

Output:
[1, 5, 8, 10, 12, 18, 20, 30]

Algorithm:

  • Create an arr3[] to store all sorted elements
  • Loop through arr1[] and arr2[] and compare each element to both the arrays
  • Copy smaller element from arr1[] and arr2[] to arr3[] and move ahead in arr3[] and in the array whose element was picked.
  • At last, if some elements were left, copy them in arr3[] as well.

1. Java

public class MergeSortedArray {

	public static void main(String[] args) {
		int arr[] = { 10, 20, 30 };
		int arr1[] = { 1, 5, 8, 12, 18 };
		System.out.println(Arrays.toString(mergeArray(arr, arr1)));
	}

	private static int[] mergeArray(int[] arr, int arr1[]) {
		int[] mergedArray = new int[arr.length + arr1.length];

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

		while (i < arr.length && j < arr1.length) {
			if (arr[i] < arr1[j]) {
				mergedArray[k] = arr[i];
				i++;
			} else {
				mergedArray[k] = arr1[j];
				j++;
			}
			k++;
		}

		while (i < arr.length) {
			mergedArray[k] = arr[i];
			i++;
			k++;
		}

		while (j < arr1.length) {
			mergedArray[k] = arr1[j];
			j++;
			k++;
		}

		return mergedArray;
	}

}

Output:

[1, 5, 8, 10, 12, 18, 20, 30]

Complete Java Solutions can be found here: Github Link

The complete list can be found here: Practise Programming Questions