Introduction

Merging two sorted arrays into one sorted array is a classic linear-time problem. Because the inputs are already ordered, the efficient solution is not to concatenate and sort again, but to walk through both arrays with pointers and always take the smaller next element.

The Standard Two-Pointer Algorithm

The basic idea is simple: keep one index in each array, compare the current values, append the smaller one, and advance the corresponding index.

1def merge_sorted(a, b):
2    i = 0
3    j = 0
4    result = []
5
6    while i < len(a) and j < len(b):
7        if a[i] <= b[j]:
8            result.append(a[i])
9            i += 1
10        else:
11            result.append(b[j])
12            j += 1
13
14    result.extend(a[i:])
15    result.extend(b[j:])
16    return result
17
18
19print(merge_sorted([1, 3, 5], [2, 4, 6]))

This runs in O(n + m) time because each element is visited once. The result uses O(n + m) extra space because it creates a new array.

Why This Is Better Than Concatenate Then Sort

It is tempting to write:

def slow_merge(a, b):
    return sorted(a + b)

That works, but it ignores the fact that the inputs are already sorted. Sorting the combined array costs more work than necessary. The two-pointer approach preserves the precondition and gets the best linear-time result.

In interviews this distinction matters for algorithmic complexity. In real systems it matters for throughput when the arrays are large or the merge happens repeatedly.

C++ Version with Reserved Capacity

The same idea translates directly to C++. Reserving output capacity avoids repeated reallocations.

1#include <iostream>
2#include <vector>
3
4std::vector<int> merge_sorted(const std::vector<int>& a, const std::vector<int>& b) {
5    std::vector<int> result;
6    result.reserve(a.size() + b.size());
7
8    std::size_t i = 0;
9    std::size_t j = 0;
10
11    while (i < a.size() && j < b.size()) {
12        if (a[i] <= b[j]) {
13            result.push_back(a[i++]);
14        } else {
15            result.push_back(b[j++]);
16        }
17    }
18
19    while (i < a.size()) result.push_back(a[i++]);
20    while (j < b.size()) result.push_back(b[j++]);
21
22    return result;
23}

The logic is identical: compare, append, advance, then copy leftovers.

In-Place Merge When One Array Has Extra Space

Some problems define the first array as having enough trailing capacity to hold the second. In that case, merge from the end so you do not overwrite values you still need to read.

1def merge_in_place(nums1, m, nums2, n):
2    i = m - 1
3    j = n - 1
4    k = m + n - 1
5
6    while j >= 0:
7        if i >= 0 and nums1[i] > nums2[j]:
8            nums1[k] = nums1[i]
9            i -= 1
10        else:
11            nums1[k] = nums2[j]
12            j -= 1
13        k -= 1
14
15
16values = [1, 2, 4, 0, 0, 0]
17merge_in_place(values, 3, [2, 5, 6], 3)
18print(values)

This uses constant extra space and is the right approach for the common "merge sorted array" interview variant.

Edge Cases Worth Testing

Even though the algorithm is small, a few cases reveal most bugs:

• one array is empty
• all values are equal
• negative numbers are present
• one array is much longer than the other
• all values in one array come before the other

Here is a quick check helper:

1def is_sorted(values):
2    return all(values[idx] <= values[idx + 1] for idx in range(len(values) - 1))
3
4
5merged = merge_sorted([1, 1, 3], [1, 2, 2])
6print(merged)
7print(is_sorted(merged))

Testing leftovers matters because many incorrect implementations forget to append the remaining tail once one array is exhausted.

Larger-Scale Merging

The same idea scales beyond interview exercises. Merge sort uses this pattern recursively, and external merge systems use a similar strategy when combining sorted files or streams. The data source changes, but the algorithmic idea stays the same: compare the next available element from each ordered source and take the smaller one.

That continuity is one reason the problem is worth understanding well. It appears in both classroom algorithms and real data-processing systems.

Common Pitfalls

The most common mistake is concatenating and sorting, which throws away the linear-time advantage. Another is forgetting to append leftover elements after the main comparison loop finishes. In in-place variants, developers often try to merge from the front and overwrite unread values. Comparison choice also matters: if you want stable ordering for equal elements, use <= consistently when taking from the left array first.

Summary

• Use two pointers to merge two sorted arrays in linear time.
• Append the smaller current element and advance that pointer.
• Copy the leftover tail after one array runs out.
• Merge from the back for in-place variants with extra buffer space.
• Do not concatenate and sort again unless simplicity matters more than performance.