Merge Two Sorted Arrays

What does it solve?

Given two arrays that are already sorted, combine them into a single sorted array — without sorting from scratch.

Since both inputs are sorted, the smallest remaining element is always at the front of one of the two arrays — just compare the two fronts and take the smaller, every time.

The core idea

// i tracks A, j tracks B:
while i < A.length and j < B.length:
if A[i] <= B[j]: take A[i], i++
else: take B[j], j++
// then drain whichever array still has leftovers

Complexity

Time complexity

O(n+m)

Every element from both arrays is visited and placed exactly once.

Space complexity

O(n+m)

For the new merged array. (A common variant merges in-place from the back when one array has spare trailing capacity — O(1) extra space.)

Examples & edge cases

Live animation

pointer i (array A) pointer j (array B) consumed just added to merged

Array A

Array B

Merged result

Step — of —

Pointer i (A)

—

Pointer j (B)

—

Merged so far

—

Step

—

Select an example and press Play to start.

✓ Complete

Speed Medium

Step-by-step table

Step	i	j	Comparison	Took	Merged array

C++ implementation

merge_sorted_arrays.cpp

#include <bits/stdc++.h>
using namespace std;

vector<int> mergeSortedArrays(vector<int>& A, vector<int>& B) {
    vector<int> merged;
    merged.reserve(A.size() + B.size());

    int i = 0, j = 0;
    while (i < (int)A.size() && j < (int)B.size()) {
        if (A[i] <= B[j]) merged.push_back(A[i++]);
        else            merged.push_back(B[j++]);
    }
    // drain whichever array still has leftovers
    while (i < (int)A.size()) merged.push_back(A[i++]);
    while (j < (int)B.size()) merged.push_back(B[j++]);

    return merged;
}

int main() {
    vector<int> A = {1,3,5,7};
    vector<int> B = {2,4,6,8};

    auto merged = mergeSortedArrays(A, B);
    for (int x : merged) cout << x << " ";
    cout << "\n";
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars