Coding problem · Easy · Basics

Merge Two Sorted Arrays

Easy Algorithms & data structures

Given two arrays a and b, each sorted in ascending order, return one sorted array containing all their elements.

Example 1

Input: a = [1,3,5], b = [2,4,6]
Output: [1,2,3,4,5,6]

Example 2

Input: a = [], b = [1]
Output: [1]

Hints

Hint 1

Use one index for each array.

Hint 2

Repeatedly take the smaller of the two current elements; when one array runs out, copy the rest of the other.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n + m) · Space O(n + m)

The two-pointer merge from merge sort: compare a[i] and b[j], take the smaller, advance that pointer. O(n + m), better than concatenating and re-sorting.

Reference solution

function mergeSorted(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++]);
  return out.concat(a.slice(i), b.slice(j));
}

function mergeSorted(a: number[], b: number[]): number[] {
  const out: number[] = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) out.push(a[i] <= b[j] ? a[i++] : b[j++]);
  return out.concat(a.slice(i), b.slice(j));
}

def merge_sorted(a: list[int], b: list[int]) -> list[int]:
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    return out + a[i:] + b[j:]

<?php

function mergeSorted(array $a, array $b): array
{
    $out = [];
    $i = $j = 0;
    while ($i < count($a) && $j < count($b)) {
        $out[] = $a[$i] <= $b[$j] ? $a[$i++] : $b[$j++];
    }
    return array_merge($out, array_slice($a, $i), array_slice($b, $j));
}

class Solution {
    public int[] mergeSorted(int[] a, int[] b) {
        int[] out = new int[a.length + b.length];
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length) out[k++] = a[i] <= b[j] ? a[i++] : b[j++];
        while (i < a.length) out[k++] = a[i++];
        while (j < b.length) out[k++] = b[j++];
        return out;
    }
}

Was this page helpful?