Merge two sorted arrays into a new array
Problem
Merge two sorted arrays into a single new sorted array.
Example 1
Input: a = [1, 3, 5], b = [2, 4, 6, 8] Output: [1, 2, 3, 4, 5, 6, 8]
Also asked as: merge 2 sorted arrays
Test cases
Case 1
Input: [1,3,5], [2,4,6,8] Expected: [1,2,3,4,5,6,8]
Case 2
Input: [1,1], [1] Expected: [1,1,1]
Case 3
Input: [], [1] Expected: [1]
Case 4
Input: [], [] Expected: []
View solutionHide solution1 approach
1. Two pointers
Time O(n + m)Space O(n + m)
Repeatedly take the smaller head of the two arrays.
function merge(a, b) { const out = []; let i = 0, j = 0; while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]); while (i < a.length) out.push(a[i++]); while (j < b.length) out.push(b[j++]); return out;}