Merge two sorted arrays into a new array

Easy

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: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}