Merge two sorted arrays in O(n+m) time and O(m+n) extra space

Given two sorted arrays, A1, A2 the task is to merge them in a sorted manner. We can solve this problem in O(n1+n2) time and O(n1+n2) extra space. The idea is to have a bigger array of size n1+n2, now traverse A1 and A2 simultaneously to put smaller of the two first in the third array.

Input: {1, 3, 5, 7} {2, 4, 6, 8}
Output: {1, 2, 3, 4, 5, 6, 7, 8}

package com.cd.array;

import java.util.Arrays;

public class MergeSortedArray {

	private static int[] merge(int[] arr1, int[] arr2) {

		int[] tmp = new int[arr1.length + arr2.length];

		int i = 0, j = 0, k = 0;
		while (j < arr1.length && k < arr2.length) {
			if (arr1[j] < arr2[k]) {
				tmp[i] = arr1[j];
				j++;
			} else {
				tmp[i] = arr2[k];
				k++;
			}
			i++;
		}

		while (j < arr1.length) {
			tmp[i] = arr1[j];
			j++;
			i++;
		}

		while (k < arr2.length) {
			tmp[i] = arr2[k];
			k++;
			i++;
		}
		return tmp;
	}

	public static void main(String[] args) {
		int[] arr1 = {1, 3, 5, 7};
		int[] arr2 = {2, 4, 6, 8};

		System.out.println("Array 1: ");
		print(arr1);
		System.out.println();

		System.out.println("Array 2: ");
		print(arr2);
		System.out.println();

		int[] merged = merge(arr1, arr2);

		System.out.println("Merged Array: ");
		print(merged);

	}

	private static void print(int[] arr) {
		Arrays.stream(arr).forEach(i -> System.out.print(i + ", "));
	}

}
Output: The output of above example will look something like this:


Array 1: 
1, 3, 5, 7, 
Array 2: 
2, 4, 6, 8, 
Merged Array: 
1, 2, 3, 4, 5, 6, 7, 8,