Merge Two Sorted Arrays

Given two arrays that are each sorted in ascending order, return a single array that contains all of their elements, also sorted in ascending order.

Example 1

Text

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

Example 2

Text

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

Brute force: concatenate, then sort

Put both arrays together and sort the result. This works for any two arrays, sorted or not.

Java

import java.util.Arrays;

public class Main {
    static int[] merge(int[] a, int[] b) {
        int[] merged = new int[a.length + b.length];
        System.arraycopy(a, 0, merged, 0, a.length);
        System.arraycopy(b, 0, merged, a.length, b.length);
        Arrays.sort(merged);
        return merged;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(merge(new int[]{1, 3, 4, 5}, new int[]{2, 6, 7, 8})));
        System.out.println(Arrays.toString(merge(new int[]{1, 1, 9}, new int[]{})));
    }
}

Output

[1, 2, 3, 4, 5, 6, 7, 8]
[1, 1, 9]

Time: O((n + m) log(n + m)). Space: O(n + m) for the result. The sort does not use the fact that both inputs are already in order.

Optimal: two pointers

The smallest remaining element is always at the front of a or at the front of b. Keep an index into each array, take the smaller front element, and advance that index. When one array runs out, the rest of the other array is already sorted, so copy it over.

Walkthrough with a = [1, 3, 4, 5], b = [2, 6, 7, 8]:

i	j	a[i]	b[j]	take	merged
0	0	1	2	1 from a	[1]
1	0	3	2	2 from b	[1, 2]
1	1	3	6	3 from a	[1, 2, 3]
2	1	4	6	4 from a	[1, 2, 3, 4]
3	1	5	6	5 from a	[1, 2, 3, 4, 5]
4	1	end	6	copy b[1..]	[1, 2, 3, 4, 5, 6, 7, 8]

Java

import java.util.Arrays;

public class Main {
    static int[] merge(int[] a, int[] b) {
        int[] merged = 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]) {
                merged[k++] = a[i++];
            } else {
                merged[k++] = b[j++];
            }
        }
        while (i < a.length) merged[k++] = a[i++]; // at most one of these two loops runs
        while (j < b.length) merged[k++] = b[j++];
        return merged;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(merge(new int[]{1, 3, 4, 5}, new int[]{2, 6, 7, 8})));
        System.out.println(Arrays.toString(merge(new int[]{1, 1, 9}, new int[]{})));
        System.out.println(Arrays.toString(merge(new int[]{-5, 0, 0}, new int[]{-6, 0, 10})));
    }
}

Output

[1, 2, 3, 4, 5, 6, 7, 8]
[1, 1, 9]
[-6, -5, 0, 0, 0, 10]

Time: O(n + m): each element is written exactly once. Space: O(n + m) for the result, which is the output and usually does not count as extra space.

Using <= takes the element from a first when the values are equal. That keeps the merge stable (equal elements keep their relative order), which merge sort relies on.

Variant: merge in place (LeetCode 88)

In LeetCode 88, a has m real elements followed by n zeros of free space, and b has to be merged into a in place. Filling from the front would overwrite values in a that haven't been read yet. Filling from the back is safe, because the largest elements go into the free slots first.

Java

import java.util.Arrays;

public class Main {
    static void mergeInPlace(int[] a, int m, int[] b) {
        int i = m, j = b.length, write = a.length; // exclusive ends
        while (j > 0) {
            if (i > 0 && a[i - 1] > b[j - 1]) {
                a[write - 1] = a[i - 1];
                i--;
            } else {
                a[write - 1] = b[j - 1];
                j--;
            }
            write--;
        }
        // Once b is used up, the rest of a is already in place.
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 0, 0, 0};
        mergeInPlace(a, 3, new int[]{2, 5, 6});
        System.out.println(Arrays.toString(a));
    }
}

Output

[1, 2, 2, 3, 5, 6]

Time: O(n + m). Space: O(1).

Edge cases

One array empty: the loop does not run, and the other array is copied as is.
Duplicates across arrays: all copies are kept.
Very different lengths: still O(n + m). If one array is tiny and the other is huge, a binary search for each small element can be faster.