Merge sorted arrays

You are midway through a Microsoft phone screen when the interviewer asks: "Given two sorted arrays, merge them into a single sorted array." This problem, also known as Merge Sorted Array, is the building block behind merge sort and a staple of sorting-category interviews. Getting it right quickly shows you understand two-pointer traversal and can write clean, linear-time code.

TL;DR

Walk two pointers through both input arrays simultaneously. At each step, compare the current elements and copy the smaller one into a new output array. When one input is exhausted, copy the rest of the other. This runs in O(n+m) time and O(n+m) space.

Why This Problem Matters

The merge step is the core operation inside merge sort, one of the most important sorting algorithms in computer science. Understanding how to merge two sorted sequences also prepares you for problems like merging k sorted lists, merge intervals, and finding the median of two sorted arrays. If you can write a clean merge function, you have a reusable building block for a whole family of harder problems.

Understanding the Problem

We need to write a method that:

• Takes two sorted arrays as input (ascending order)
• Returns a new array containing all elements from both inputs, in sorted order

mergeSorted([2,5,7,8,9], [9])      -> [2,5,7,8,9,9]
mergeSorted([7,8], [1,2])          -> [1,2,7,8]
mergeSorted([2], [])               -> [2]

Edge Cases

1. One or both arrays empty: Return the non-empty array (or an empty array if both are empty)
2. All elements in one array are smaller: The comparison loop drains the first array, then the copy loop handles the second
3. Duplicate values across arrays: Both copies of the value end up adjacent in the output
4. Arrays of different lengths: The shorter array is exhausted first, and the remaining elements of the longer array are copied over

Solution Approach

The key insight is that both arrays are already sorted. Instead of concatenating them and re-sorting (which would waste the existing ordering), we can walk through both arrays in lockstep, always picking the smaller of the two current elements.

Here is how the merge of [2,5,7] and [1,4,8] plays out:

At each step, we compare the elements at idx1 and idx2. The smaller element goes into the merged array, and that pointer advances. Once arr1 is exhausted after step 4, the remaining element from arr2 (the 8) is copied directly.

When one array is empty, the merge loop is skipped entirely:

The comparison while never executes because arr2 has no elements. The copy loop for arr1 handles everything.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int[] mergeSorted(int[] arr1, int[] arr2) {
    int[] merged = new int[arr1.length + arr2.length];

    int idx1 = 0, idx2 = 0, mergedIdx = 0;

    while (idx1 < arr1.length && idx2 < arr2.length) {
      merged[mergedIdx++] = arr1[idx1] < arr2[idx2] ? arr1[idx1++] : arr2[idx2++];
    }

    while (idx1 < arr1.length) {
      merged[mergedIdx++] = arr1[idx1++];
    }

    while (idx2 < arr2.length) {
      merged[mergedIdx++] = arr2[idx2++];
    }

    return merged;
  }
}

Let's walk through the code:

1. Allocate the output array: Its size is the sum of both input lengths since every element must appear in the result
2. Three pointers: idx1 tracks position in arr1, idx2 tracks position in arr2, and mergedIdx tracks where to write next in the output
3. Main comparison loop: While both arrays still have elements, compare arr1[idx1] and arr2[idx2]. The smaller value goes into merged[mergedIdx], and both the source pointer and the write pointer advance
4. Drain remaining elements: After the main loop, at most one array still has leftover elements. Two simple while loops handle each case

Handling Duplicates

When both pointers point to equal values, the < comparison evaluates to false, so the element from arr2 is picked first. This is fine because the merged result just needs both values adjacent to each other. Here is the trace for [2,5,7,8] and [2,4,7,12,32]:

At step 0, both arrays have the value 2. Since 2 < 2 is false, the else branch picks arr2[0]. Then at step 1, arr1[0] (also 2) is picked next. Both copies of 2 end up at the front of the merged result.

Complexity Analysis

Time: O(n+m) where n is the length of arr1 and m is the length of arr2. Each element is visited exactly once across the three loops. The comparison loop processes elements from both arrays simultaneously, and the drain loops process whatever remains.

Space: O(n+m). The merged output array holds all n+m elements. No other data structures are used beyond the three pointer variables.

Why Not Concatenate and Sort?

You could append both arrays and call a sorting algorithm:

int[] combined = new int[arr1.length + arr2.length];
System.arraycopy(arr1, 0, combined, 0, arr1.length);
System.arraycopy(arr2, 0, combined, arr1.length, arr2.length);
Arrays.sort(combined);
return combined;

This works, but runs in O((n+m) log(n+m)) time. The two-pointer approach is strictly better at O(n+m) because it takes advantage of the pre-sorted inputs. In an interview, mentioning this tradeoff shows you understand algorithmic efficiency.

Common Pitfalls

1. Forgetting the drain loops: After the main comparison loop, one array may still have elements. Without the two trailing while loops, those elements are lost and the output array contains trailing zeros.

2. Using <= instead of <: Using <= in the comparison changes which array an equal element is pulled from, but it does not affect correctness. However, be consistent. If asked about stability (preserving the relative order of equal elements from the same source), know which branch handles ties.

3. Off-by-one with array sizing: The merged array must have exactly arr1.length + arr2.length slots. Allocating fewer causes an ArrayIndexOutOfBoundsException.

4. Mutating input arrays: The problem asks for a new merged array, not an in-place merge. Do not modify arr1 or arr2.

Interview Tips

When presenting this solution:

• State the approach upfront: "I will use three pointers to walk through both arrays and an output array simultaneously."
• Mention that this is the merge step of merge sort. Interviewers appreciate when you connect problems to broader algorithmic concepts.
• Draw out a small example on the whiteboard: arr1=[1,3], arr2=[2,4], and trace the pointers through each iteration.
• If asked for a follow-up, discuss merging k sorted arrays using a min-heap (priority queue) in O(N log k) time, where N is the total number of elements.

Key Takeaways

• The two-pointer technique merges two sorted arrays in O(n+m) time by comparing current elements and advancing the pointer with the smaller value.
• Always allocate the output array to the combined size of both inputs. Every element from both arrays must appear in the result.
• After the main comparison loop, exactly one of the two input arrays may still have remaining elements. Two simple drain loops handle this cleanly.
• This merge operation is the foundation of merge sort, and the same pattern appears in merging k sorted lists, merge intervals, and median of two sorted arrays.
• Avoid the temptation to concatenate and re-sort. Exploiting pre-sorted order gives you a linear-time solution instead of O((n+m) log(n+m)).

Practice and Related Problems

Once you are comfortable with merging two sorted arrays, try these progressions:

• Merge sort (apply the merge step recursively)
• Merge k sorted lists (use a min-heap to generalize beyond two inputs)
• Merge intervals (similar two-pointer logic on interval boundaries)
• Median of two sorted arrays (binary search variant on sorted inputs)

This problem and hundreds of others are available on Firecode, where consistent daily practice helps you build the pattern recognition that top tech companies look for. Whether you are warming up for phone screens or preparing for on-site interviews, starting with fundamentals like this sets you up well.

Solutions in Other Languages

Python

from typing import List


class Solution:
    def merge_sorted(self, arr1: List[int], arr2: List[int]) -> List[int]:
        merged = []

        idx1 = idx2 = 0

        while idx1 < len(arr1) and idx2 < len(arr2):
            if arr1[idx1] < arr2[idx2]:
                merged.append(arr1[idx1])
                idx1 += 1
            else:
                merged.append(arr2[idx2])
                idx2 += 1

        while idx1 < len(arr1):
            merged.append(arr1[idx1])
            idx1 += 1

        while idx2 < len(arr2):
            merged.append(arr2[idx2])
            idx2 += 1

        return merged

JavaScript

class Solution {
  mergeSorted(arr1, arr2) {
    const merged = new Array(arr1.length + arr2.length);

    let idx1 = 0, idx2 = 0, mergedIdx = 0;

    while (idx1 < arr1.length && idx2 < arr2.length) {
      merged[mergedIdx++] = arr1[idx1] < arr2[idx2] ? arr1[idx1++] : arr2[idx2++];
    }

    while (idx1 < arr1.length) {
      merged[mergedIdx++] = arr1[idx1++];
    }

    while (idx2 < arr2.length) {
      merged[mergedIdx++] = arr2[idx2++];
    }

    return merged;
  }
}

TypeScript

class Solution {
  mergeSorted(arr1: number[], arr2: number[]): number[] {
    const merged: number[] = new Array(arr1.length + arr2.length);

    let idx1 = 0, idx2 = 0, mergedIdx = 0;

    while (idx1 < arr1.length && idx2 < arr2.length) {
      merged[mergedIdx++] = arr1[idx1] < arr2[idx2] ? arr1[idx1++] : arr2[idx2++];
    }

    while (idx1 < arr1.length) {
      merged[mergedIdx++] = arr1[idx1++];
    }

    while (idx2 < arr2.length) {
      merged[mergedIdx++] = arr2[idx2++];
    }

    return merged;
  }
}

C++

#include <vector>

class Solution {
public:
  std::vector<int> mergeSorted(std::vector<int> arr1, std::vector<int> arr2) {
    std::vector<int> merged(arr1.size() + arr2.size());

    int idx1 = 0, idx2 = 0, mergedIdx = 0;

    while (idx1 < arr1.size() && idx2 < arr2.size()) {
      merged[mergedIdx++] = arr1[idx1] < arr2[idx2] ? arr1[idx1++] : arr2[idx2++];
    }

    while (idx1 < arr1.size()) {
      merged[mergedIdx++] = arr1[idx1++];
    }

    while (idx2 < arr2.size()) {
      merged[mergedIdx++] = arr2[idx2++];
    }

    return merged;
  }
};

Go

package solution

func (s *Solution) MergeSorted(arr1 []int, arr2 []int) []int {
    merged := make([]int, len(arr1)+len(arr2))

    idx1, idx2, mergedIdx := 0, 0, 0

    for idx1 < len(arr1) && idx2 < len(arr2) {
        if arr1[idx1] < arr2[idx2] {
            merged[mergedIdx] = arr1[idx1]
            idx1++
        } else {
            merged[mergedIdx] = arr2[idx2]
            idx2++
        }
        mergedIdx++
    }

    for idx1 < len(arr1) {
        merged[mergedIdx] = arr1[idx1]
        mergedIdx++
        idx1++
    }

    for idx2 < len(arr2) {
        merged[mergedIdx] = arr2[idx2]
        mergedIdx++
        idx2++
    }

    return merged
}

Scala

class Solution {
  def mergeSorted(arr1: Array[Int], arr2: Array[Int]): Array[Int] = {
    val merged = new Array[Int](arr1.length + arr2.length)

    var idx1 = 0
    var idx2 = 0
    var mergedIdx = 0

    while (idx1 < arr1.length && idx2 < arr2.length) {
      if (arr1(idx1) < arr2(idx2)) {
        merged(mergedIdx) = arr1(idx1)
        idx1 += 1
      } else {
        merged(mergedIdx) = arr2(idx2)
        idx2 += 1
      }
      mergedIdx += 1
    }

    while (idx1 < arr1.length) {
      merged(mergedIdx) = arr1(idx1)
      mergedIdx += 1
      idx1 += 1
    }

    while (idx2 < arr2.length) {
      merged(mergedIdx) = arr2(idx2)
      mergedIdx += 1
      idx2 += 1
    }

    merged
  }
}

Kotlin

class Solution {
    fun mergeSorted(arr1: IntArray, arr2: IntArray): IntArray {
        val merged = IntArray(arr1.size + arr2.size)

        var idx1 = 0
        var idx2 = 0
        var mergedIdx = 0

        while (idx1 < arr1.size && idx2 < arr2.size) {
            merged[mergedIdx++] = if (arr1[idx1] < arr2[idx2]) arr1[idx1++] else arr2[idx2++]
        }

        while (idx1 < arr1.size) {
            merged[mergedIdx++] = arr1[idx1++]
        }

        while (idx2 < arr2.size) {
            merged[mergedIdx++] = arr2[idx2++]
        }

        return merged
    }
}

Swift

import Foundation

class Solution {
    func mergeSorted(_ arr1: [Int], _ arr2: [Int]) -> [Int] {
        var merged = [Int](repeating: 0, count: arr1.count + arr2.count)

        var idx1 = 0
        var idx2 = 0
        var mergedIdx = 0

        while idx1 < arr1.count && idx2 < arr2.count {
            if arr1[idx1] < arr2[idx2] {
                merged[mergedIdx] = arr1[idx1]
                idx1 += 1
            } else {
                merged[mergedIdx] = arr2[idx2]
                idx2 += 1
            }
            mergedIdx += 1
        }

        while idx1 < arr1.count {
            merged[mergedIdx] = arr1[idx1]
            idx1 += 1
            mergedIdx += 1
        }

        while idx2 < arr2.count {
            merged[mergedIdx] = arr2[idx2]
            idx2 += 1
            mergedIdx += 1
        }

        return merged
    }
}

Rust

impl Solution {
    pub fn merge_sorted(&self, arr1: Vec<i32>, arr2: Vec<i32>) -> Vec<i32> {
        let mut merged: Vec<i32> = vec![0; arr1.len() + arr2.len()];

        let mut idx1 = 0;
        let mut idx2 = 0;
        let mut merged_idx = 0;

        while idx1 < arr1.len() && idx2 < arr2.len() {
            if arr1[idx1] < arr2[idx2] {
                merged[merged_idx] = arr1[idx1];
                idx1 += 1;
            } else {
                merged[merged_idx] = arr2[idx2];
                idx2 += 1;
            }
            merged_idx += 1;
        }

        while idx1 < arr1.len() {
            merged[merged_idx] = arr1[idx1];
            idx1 += 1;
            merged_idx += 1;
        }

        while idx2 < arr2.len() {
            merged[merged_idx] = arr2[idx2];
            idx2 += 1;
            merged_idx += 1;
        }

        merged
    }
}

C#

public class Solution {
    public int[] mergeSorted(int[] arr1, int[] arr2) {
        int[] merged = new int[arr1.Length + arr2.Length];

        int idx1 = 0, idx2 = 0, mergedIdx = 0;

        while (idx1 < arr1.Length && idx2 < arr2.Length) {
            merged[mergedIdx++] = arr1[idx1] < arr2[idx2] ? arr1[idx1++] : arr2[idx2++];
        }

        while (idx1 < arr1.Length) {
            merged[mergedIdx++] = arr1[idx1++];
        }

        while (idx2 < arr2.Length) {
            merged[mergedIdx++] = arr2[idx2++];
        }

        return merged;
    }
}

Dart

class Solution {
  List<int> mergeSorted(List<int> arr1, List<int> arr2) {
    List<int> merged = List.filled(arr1.length + arr2.length, 0);

    int idx1 = 0, idx2 = 0, mergedIdx = 0;

    while (idx1 < arr1.length && idx2 < arr2.length) {
      merged[mergedIdx++] = arr1[idx1] < arr2[idx2] ? arr1[idx1++] : arr2[idx2++];
    }

    while (idx1 < arr1.length) {
      merged[mergedIdx++] = arr1[idx1++];
    }

    while (idx2 < arr2.length) {
      merged[mergedIdx++] = arr2[idx2++];
    }

    return merged;
  }
}

PHP

class Solution {
    public function mergeSorted(array $arr1, array $arr2): array {
        $merged = [];
        $idx1 = 0;
        $idx2 = 0;
        $len1 = count($arr1);
        $len2 = count($arr2);

        while ($idx1 < $len1 && $idx2 < $len2) {
            $merged[] = $arr1[$idx1] < $arr2[$idx2] ? $arr1[$idx1++] : $arr2[$idx2++];
        }

        while ($idx1 < $len1) {
            $merged[] = $arr1[$idx1++];
        }

        while ($idx2 < $len2) {
            $merged[] = $arr2[$idx2++];
        }

        return $merged;
    }
}

Ruby

class Solution
  def merge_sorted(arr1, arr2)
    merged = []

    idx1 = 0
    idx2 = 0

    while idx1 < arr1.length && idx2 < arr2.length
      if arr1[idx1] < arr2[idx2]
        merged << arr1[idx1]
        idx1 += 1
      else
        merged << arr2[idx2]
        idx2 += 1
      end
    end

    merged.concat(arr1[idx1..-1])

    merged.concat(arr2[idx2..-1])

    merged
  end
end