Merging Two Sorted Arrays Into One

Merging Two Sorted Arrays Into One

Imagine you have two lists of numbers. Both lists are already neatly sorted from smallest to largest. Your job is to combine them into a single list that is *also* sorted from smallest to largest. This is one of the most common building-block problems in programming, and once you understand it, many harder problems become easier.

What "sorted in non-decreasing order" means

A list is in non-decreasing order when each number is greater than or equal to the one before it. So [1, 2, 3] is sorted, and so is [1, 1, 2] (equal values are allowed). The word "non-decreasing" simply means "the numbers never go down as you move right."

The exact problem

You are given:

• arr1 — the first sorted array.
• arr2 — the second sorted array.
• m — how many *real* numbers are stored at the front of arr1.
• n — how many *real* numbers are in arr2.

The twist is that arr1 is bigger than it needs to be. It has the m real numbers at the front, followed by n empty slots (shown as 0s). Those 0s are just placeholders — extra room reserved so the result can fit. You must place all the numbers from arr2 into arr1 so that arr1 ends up holding all m + n numbers in sorted order. This is called doing it in place, meaning you reuse the same arr1 instead of building a brand-new array.

A worked example

Look at Example 1:

Input:  arr1 = [1, 2, 3, 0, 0], m = 3, arr2 = [4, 5], n = 2
Output: [1, 2, 3, 4, 5]

Here arr1 has 3 real numbers (1, 2, 3) and 2 placeholder slots (0, 0). The array arr2 has 2 numbers (4, 5). After merging, arr1 should become [1, 2, 3, 4, 5] — all five numbers sorted together. The placeholders are gone because we filled them with real numbers.

Why there is extra space

The problem promises that arr1 always has at least m + n slots — enough room to hold its own numbers plus everything from arr2. That is why you can safely write the merged result back into arr1 without running out of space.

The intuition behind merging

Think of two stacks of cards, each already sorted with the smallest card on top. To merge them, you keep comparing the top card of each stack and take the smaller one. You repeat this until both stacks are empty. Because both inputs are already sorted, you never have to look back — the next smallest card is always sitting on top of one of the two stacks.

A clever trick for this specific problem is to fill arr1 from the back. The empty slots are at the end, so you place the *largest* numbers there first, working from the biggest down to the smallest. This way you never overwrite a real number before you have used it.

The function you must complete

using namespace std;
class Solution {
public:
    void mergeSortedArrays(
        vector<int> &arr1, int m,
        vector<int> &arr2, int n
    ) {
    }
};

The function returns void (nothing) because the answer is the modified arr1 itself. Note the & on vector<int> &arr1 — it means you are working on the real array, so any change you make stays after the function ends.