easyArray ProblemsJava

Merge Two Sorted Arrays Into One Sorted Array

Combine two sorted arrays into a single sorted array.

Quick Answer

Keep one pointer per input array. Repeatedly compare the two front elements and copy the smaller one into the result, advancing that pointer. When one array runs out, copy the rest of the other. This produces a fully sorted merged array in O(m + n) time.

Problem Statement

Given two arrays that are each already sorted in ascending order, produce a single new array containing all their elements in ascending order. Duplicates across the two arrays are all kept.

For example, merging [1, 3, 5] and [2, 4, 6] gives [1, 2, 3, 4, 5, 6].

Input: Two ascending-sorted integer arrays a (length m) and b (length n).

Output: A new ascending-sorted array of length m + n with every element.

Examples

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

The two-pointer merge interleaves the arrays in sorted order.

Example 2
Input:  a = [2, 8], b = [1, 3, 9]
Output: [1, 2, 3, 8, 9]

1 comes first from b, then 2 from a, then 3 from b, and so on.

Constraints

  • 0 <= m, n <= 10^6
  • Both inputs are sorted in non-decreasing order

Think Before You Code

Reveal the questions to ask yourself first
  • Since both inputs are already sorted, do you actually need to sort anything?
  • How do you always pick the next smallest element across both arrays?
  • What must happen once one array is exhausted but the other still has elements?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
Because both arrays are sorted, the next element of the answer is always the smaller of the two current fronts.
Hint 2
Track index `i` into `a` and `j` into `b`; compare `a[i]` and `b[j]` and copy the smaller, then advance that index.
Hint 3
When one pointer reaches the end, append every remaining element of the other array unchanged.

Approach

Reveal the step-by-step approach

A linear merge, exactly the combine step of merge sort.

  1. Allocate a result array of size m + n and set i = j = k = 0.
  2. While both i < m and j < n: if a[i] <= b[j], put a[i] into result[k] and advance i; otherwise put b[j] and advance j. Advance k.
  3. Copy any leftover elements of a (from i) into the result.
  4. Copy any leftover elements of b (from j) into the result.

Using <= in the comparison keeps equal elements in their original order (a stable merge).

Dry Run

Walk through the example step by step

Merging a = [2, 8], b = [1, 3, 9]:

i | j | a[i] | b[j] | pick | result
--+---+------+------+------+-----------------
0 | 0 | 2    | 1    | b:1  | [1]
0 | 1 | 2    | 3    | a:2  | [1,2]
1 | 1 | 8    | 3    | b:3  | [1,2,3]
1 | 2 | 8    | 9    | a:8  | [1,2,3,8]
2 | 2 | -    | 9    | b:9  | [1,2,3,8,9]  (a exhausted, copy rest of b)

Solution

Reveal the full Java solution
import java.util.Arrays;

public class MergeSortedArrays {
    public static int[] merge(int[] a, int[] b) {
        int[] result = 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]) {
                result[k++] = a[i++];
            } else {
                result[k++] = b[j++];
            }
        }
        while (i < a.length) {
            result[k++] = a[i++];
        }
        while (j < b.length) {
            result[k++] = b[j++];
        }
        return result;
    }

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

The merge exploits the fact that both inputs are sorted: at each step the overall smallest unplaced value must be one of the two current fronts, so a single comparison suffices. Each element is copied exactly once, so the total work is O(m + n), and the result array is the only extra allocation.

Time: O(m + n)Space: O(m + n) for the result array

Common Mistakes

  • Concatenating both arrays and calling a full sort, which is O((m+n) log(m+n)) and wastes the sorted inputs.
  • Forgetting one of the tail-copy loops, so trailing elements of the longer array are dropped.

Edge Cases to Test

  • One array empty should return a copy of the other.
  • Both arrays empty should return an empty array.
  • Equal elements across arrays must all appear in the result.

Interview Follow-Ups

  • How would you merge in place when `a` has trailing space to hold all of `b`?
  • How would you merge k sorted arrays efficiently?
  • How does this merge step drive the overall O(n log n) cost of merge sort?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us