To merge two sorted arrays in one sorted array, you can loop through the elements of both arrays and compare them. Put the smaller one in the output array. When one array reaches the end, move the rest of elements of the other array into the output array.
Interview Question:
Merge two sorted array into one sorted array. How to improve it?
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
import java.util.Arrays; public class MergeTwoSortedArrays { //Solution 1, Return new array, Time O(m+n), Space O(m+n), //m and n are the lengths of two arrays public static int[] mergeSortedArray(int[] a, int[] b) { int[] res = new int[a.length + b.length]; int i = 0, j = 0, k = 0; while (i < a.length && j < b.length) { if (a[i] < b[j]) res[k++] = a[i++]; else res[k++] = b[j++]; } while (i < a.length) res[k++] = a[i++]; while (j < b.length) res[k++] = b[j++]; return res; } //Solution 2, Merge in place, Time O(m+n), Space O(1) public static void mergeInPlace(int[] a, int[] b, int m, int n) { int k = m + n - 1; int i = m - 1; int j = n - 1; while (j >= 0 && i >= 0) { if (a[i] > b[j]) a[k--] = a[i--]; else a[k--] = b[j--]; } } public static void main(String[] args) { //Solution 1, Return new array int[] a = {0, 4, 5, 19, 21, 33, 36, 38, 61}; int[] b = {1, 2, 7, 30, 40}; int[] res = mergeSortedArray(a, b); System.out.print("Merge (new array): "); System.out.println(Arrays.toString(res)); //Solution 2, Merge in place int[] a1 = {0, 4, 5, 19, 21, 33, 36, 38, 61, 0, 0, 0, 0, 0}; int m = 9; int[] b1 = {1, 2, 7, 30, 40}; int n = 5; mergeInPlace(a1, b1, m, n); System.out.print("Merge (in place): "); System.out.println(Arrays.toString(a1)); } } |
Javascript
|
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 34 35 36 37 38 39 40 |
//Solution 1, Return new array, Time O(m+n), Space O(m+n), //m and n are the lengths of two arrays function mergeSortedArray(a, b) { var res = new Array(a.length + b.length); var i = 0, j = 0, k = 0; while (i < a.length && j < b.length) { if (a[i] < b[j]) res[k++] = a[i++]; else res[k++] = b[j++]; } while (i < a.length) res[k++] = a[i++]; while (j < b.length) res[k++] = b[j++]; return res; } //Solution 2, Merge in place, Time O(m+n), Space O(1) function mergeInPlace(a, b, m, n) { var k = m + n - 1; var i = m - 1; var j = n - 1; while (j >= 0 && i >= 0) { if (a[i] > b[j]) a[k--] = a[i--]; else a[k--] = b[j--]; } } let a = [0, 4, 5, 19, 21, 33, 36, 38, 61]; let b = [1, 2, 7, 30, 40]; let res = mergeSortedArray(a, b); console.log("Merge (new array): " + res); //Solution 2, Merge in place let a1 = [0, 4, 5, 19, 21, 33, 36, 38, 61, 0, 0, 0, 0, 0]; let m = 9; let b1 = [1, 2, 7, 30, 40]; let n = 5; mergeInPlace(a1, b1, m, n); console.log("Merge (in place): " + a1); |
Python
|
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 34 35 36 37 38 39 |
#Solution 1, Return new array, Time O(m+n), Space O(m+n), #m and n are the lengths of two arrays def mergeSortedArray(a, b): res = [] while (a and b): if (a[0] <= b[0]): # Compare both heads item = a.pop(0) # Pop from the head res.append(item) else: item = b.pop(0) res.append(item) res.extend(a if a else b) return res #Solution 2, Merge in place, Time O(m+n), Space O(1) def mergeInPlace(a, b, m, n) : k = m + n - 1 i = m - 1 j = n - 1 while j >= 0 and i >= 0: if a[i] > b[j]: a[k] = a[i] k-=1 i-=1 else: a[k] = b[j] k-=1 j-=1 l1 = [0,4,5,19,21,33,36,38,61] l2 = [1, 2, 7,30,40] print("Merge (new array): ") print(mergeSortedArray(l1, l2)) a1 = [0, 4, 5, 19, 21, 33, 36, 38, 61, 0, 0, 0, 0, 0] m = 9 b1 = [1, 2, 7, 30, 40] n = 5 mergeInPlace(a1, b1, m, n) print("Merge (in place): ") print (a1) |
Output:
Array 1: 0 4 5 19 21 33 36 38 61
Array 2: 1 2 7 30 40
Merge (new array): 0 1 2 4 5 7 19 21 30 33 36 38 40 61
Array 1: 0 4 5 19 21 33 36 38 61 0 0 0 0 0
Array 2: 1 2 7 30 40
Merge (in place): 0 1 2 4 5 7 19 21 30 33 36 38 40 61
O Notation:
Solution 1:
Time Complexity : O(m+n), Space Complexity : O(m+n)
Solution 2:
Time Complexity : O(m+n), Space Complexity : O(1)
Download MergeTwoSortedArrays.java
Download MergeTwoSortedArrays.js
Download MergeTwoSortedArrays.py
In merge in–space, you declare one of the array to have enough space to hold the elements in the other array. When merging, you start from the last elements of the arrays and compare them. Put the larger one in the last spot of the output array, then move to the front. Since you don’t need extra memory space, merge in place can improve the space complexity from O(m+n) to O(1).
