# 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,
``````