Merge Sorted Array DSA: Brute Force, Merge Copy, and the Three-Pointer Trick

Learn Merge Sorted Array DSA the beginner-friendly way. Compare brute force, merge copy, and the in-place three-pointer trick with dry runs and clean code.

1. Introduction

Merge Sorted Array DSA is one of those problems that looks easy, then trips you up on the details. You get two sorted arrays, and you have to blend them into one sorted array. The twist is where the answer must live, and that small rule changes everything.

Here is the task in plain words. You get two arrays that are already sorted. The first one has extra empty space at the end, just enough to hold the second array. Your job is to pour the second array into the first, and keep the whole thing sorted.

In this guide we go slow. First we try the easy way, which is to dump and sort. Then we copy into a fresh array like a careful librarian. Finally we reach the clever three-pointer trick that fills the array from the back with no extra space. We dry run each idea by hand, so you can watch it click.

2. Understanding the Problem

Let us pin down the rules first. This problem hides a few traps, and a clear statement keeps you safe.

• You get nums1 and nums2, both sorted in non-decreasing order.
• nums1 has a length of m plus n. The first m slots hold real values, and the last n slots are zeros, just placeholders.
• nums2 has n real values.
• Merge nums2 into nums1 so that nums1 ends up fully sorted.
• The change happens in place. You do not return a new array.

Take nums1 = [1, 2, 3, 0, 0, 0] with m = 3, and nums2 = [2, 5, 6] with n = 3. After merging, nums1 should be [1, 2, 2, 3, 5, 6]. Those trailing zeros are not real data. They are just room to grow, so do not treat them as values to sort.

3. Concepts You Need Here

Before the code, let us name the ideas that carry this problem. Each one is small, and you will reuse them in many array questions.

3.1 Two Sorted Inputs

Both arrays are already sorted. That is a gift. When two lists are sorted, you can walk them side by side and always know which next value is smaller. So you never need a full re-sort if you are careful.

3.2 Filling From the Back

The empty room sits at the end of nums1. So the safest place to write is the back, not the front. If you write from the front, you might stomp on a value you still need to read. Filling from the back avoids that clash. That single insight is the heart of the best solution.

4. Approach 1: Brute Force (Dump and Sort)

The first idea most people reach for is blunt but honest. Copy every value from nums2 into the empty tail of nums1. Then sort the whole array and call it done.

4.1 Pseudocode

for j from 0 to n-1:
    nums1[m + j] = nums2[j]   // fill the empty tail
sort(nums1)                   // let the library sort it

Let us read that pseudocode one line at a time, in plain words.

• Line 1: the counter j walks through nums2 from the first value to the last. So j is 0, then 1, then 2 for a nums2 of size 3.
• Line 2: we copy nums2[j] into nums1 at position m + j. The first m slots of nums1 already hold real data. So the empty room starts at index m. That is why we add m. When j is 0, we write to slot m. When j is 1, we write to slot m + 1. And so on, down the tail.
• Line 3: after the loop, every value sits inside nums1, but the order is a mess. One sort call reorders the whole thing from smallest to largest.

So the plan is simple. First we pour nums2 into the empty slots. Then we let the sort clean up. It is short, and it is hard to get wrong.

4.2 Java Code

import java.util.Arrays;
 
public class MergeSortedArrayBrute {
    public static void merge(int[] nums1, int m,
                             int[] nums2, int n) {
        for (int j = 0; j < n; j++) {
            nums1[m + j] = nums2[j];
        }
        Arrays.sort(nums1);
    }
 
    public static void main(String[] args) {
        int[] nums1 = { 1, 2, 3, 0, 0, 0 };
        int[] nums2 = { 2, 5, 6 };
        merge(nums1, 3, nums2, 3);
        System.out.println(Arrays.toString(nums1));
        // [1, 2, 2, 3, 5, 6]
    }
}

4.3 Why This Works, Step by Step

Let us read the code slowly. Each line does one small job.

• The loop copies nums2 into the tail of nums1, filling those zero slots.
• After the loop, nums1 holds every value, but the order is messy.
• Arrays.sort(nums1) then reorders the whole array from small to large.
• Because nums1 already has the right size, we sort it directly with no extra array.

This version is easy to read, and it always gives the correct answer. That is its strength. The weakness is that it throws away the fact that both inputs were already sorted.

4.4 Dry Run of the Brute Force

Let us trace it with nums1 = [1, 2, 3, 0, 0, 0], m = 3, and nums2 = [2, 5, 6], n = 3. The empty slots are at indexes 3, 4, and 5. We copy first, then we sort. Read each row as one turn of the loop.

Let us read the trace slowly, so nothing feels like magic.

• Step 1: j is 0, so we grab nums2[0], which is 2. We write it at slot m + 0 = 3. The first empty zero is now a 2.
• Step 2: j is 1, so nums2[1] = 5 goes into slot m + 1 = 4. Another zero is filled.
• Step 3: j is 2, so nums2[2] = 6 goes into slot m + 2 = 5. Now every slot holds a value, and the array reads [1, 2, 3, 2, 5, 6].
• Step 4: the loop is done. Look at the array: the 2 from nums2 is stuck between 3 and 5, out of order. Arrays.sort then slides everything into place, giving [1, 2, 2, 3, 5, 6].

So the stray 2 is the whole reason we need the sort. The copy alone does not keep things ordered. That sort works, but it redoes effort, because both inputs were already sorted before we started.

4.5 Time and Space Cost

The copy loop takes O(n) time. The sort takes O((m + n) log (m + n)) time, which dominates. So the whole thing is O((m + n) log (m + n)). The space is O(1) beyond the array itself, since we sort in place. For small arrays this is fine. On big inputs, the extra log factor is wasted effort.

5. Approach 2: Merge Into a Copy

Here is a smarter middle ground. Both arrays are sorted, so let us use that. We keep a copy of the first m values. Then we merge that copy with nums2, writing results into nums1 from the front.

5.1 Pseudocode

copy = first m values of nums1
i = 0   // pointer in copy
j = 0   // pointer in nums2
k = 0   // write pointer in nums1
while i < m and j < n:
    if copy[i] <= nums2[j]:
        nums1[k++] = copy[i++]
    else:
        nums1[k++] = nums2[j++]
copy any leftover from copy or nums2

This one has more moving parts, so let us unpack each line.

• Line 1: we take a snapshot of the first m real values of nums1 and store it in copy. This backup means we can overwrite nums1 without losing anything.
• Lines 2 to 4: we set up three pointers, all starting at 0. i reads the copy, j reads nums2, and k marks the next slot to write in nums1. Here we write from the front, because the copy keeps the originals safe.
• Line 5: the while loop runs as long as both sides still have values left. The moment either the copy or nums2 runs empty, the loop stops.
• Lines 6 to 9: we compare the two front values. If copy[i] is smaller or equal, we write it and step i forward. Otherwise we write nums2[j] and step j forward. Either way k moves forward too. The plus plus means we use the value, then bump the pointer.
• Line 10: once one side empties, the other side still has sorted values waiting. We just pour those straight into nums1, no comparison needed.

The key idea: since both lists are already sorted, the smaller front value is always the next one to place. So one clean sweep is enough.

5.2 Java Code

import java.util.Arrays;
 
public class MergeSortedArrayCopy {
    public static void merge(int[] nums1, int m,
                             int[] nums2, int n) {
        int[] copy = Arrays.copyOf(nums1, m);
        int i = 0, j = 0, k = 0;
        while (i < m && j < n) {
            if (copy[i] <= nums2[j]) {
                nums1[k++] = copy[i++];
            } else {
                nums1[k++] = nums2[j++];
            }
        }
        while (i < m) nums1[k++] = copy[i++];
        while (j < n) nums1[k++] = nums2[j++];
    }
 
    public static void main(String[] args) {
        int[] nums1 = { 1, 2, 3, 0, 0, 0 };
        int[] nums2 = { 2, 5, 6 };
        merge(nums1, 3, nums2, 3);
        System.out.println(Arrays.toString(nums1));
        // [1, 2, 2, 3, 5, 6]
    }
}

5.3 Reading the Code Line by Line

Now let us map each line of Java to what it does.

• Arrays.copyOf(nums1, m) makes a fresh array holding just the first m values of nums1. That is our safe backup, called copy.
• int i = 0, j = 0, k = 0 sets all three pointers to the front. i reads copy, j reads nums2, k writes into nums1.
• while (i < m && j < n) runs while both sides still have values. The moment either pointer runs past its end, this loop stops.
• if (copy[i] <= nums2[j]) checks which front value is smaller. On a tie we take from copy, which keeps equal values in a stable order.
• nums1[k++] = copy[i++] writes copy[i] into nums1[k], then moves both k and i one step forward. The other branch does the same with nums2 and j.
• The two trailing while loops handle leftovers. If copy still has values, we drain it. If nums2 still has values, we drain that instead. Only one of them ever runs.

This finishes in one clean sweep, so the time is O(m + n). That beats the brute force sort. The catch is the extra copy array, which costs O(m) space.

5.4 Dry Run of the Copy Merge

Let us trace with copy = [1, 2, 3] and nums2 = [2, 5, 6]. All three pointers start at 0. We write into nums1 from the front. The last column shows the part we have merged so far. An underscore means we have not written that slot yet.

Let us narrate the pointer dance, step by step.

• Step 1: i and j both point at the front. We compare copy[0] = 1 with nums2[0] = 2. Since 1 is smaller, we write 1 and step i to index 1. j stays put.
• Step 2: now copy[1] = 2 meets nums2[0] = 2. It is a tie, so our rule takes from copy. We write 2 and step i to index 2.
• Step 3: copy[2] = 3 meets nums2[0] = 2. This time 2 is smaller, so we write 2 and step j to index 1. Notice i did not move here.
• Step 4: copy[2] = 3 meets nums2[1] = 5. Now 3 wins, so we write 3 and step i to index 3. That pushes i past the end of copy.
• Step 5: i has run off the end, so the while loop stops. The copy is drained, but nums2 still holds 5 and 6 in order. We pour them straight in.

Once one side empties, no more comparing is needed. Whatever is left is already sorted, so we just copy it across.

6. Approach 3: The Three-Pointer Trick

Now for the version interviewers really want. The idea is to fill nums1 from the back, using its own empty tail as the workspace. No copy array, no re-sort, just one smart pass.

Think of it like stacking boxes into a truck from the rear. You place the biggest box last, right at the very back, then work forward. Because the empty space sits at the end of nums1, the back is always safe to write.

6.1 Pseudocode

i = m - 1   // last real value in nums1
j = n - 1   // last value in nums2
k = m + n - 1   // last slot in nums1
while j >= 0:
    if i >= 0 and nums1[i] > nums2[j]:
        nums1[k--] = nums1[i--]
    else:
        nums1[k--] = nums2[j--]

This is the clever one, so let us read every line carefully.

• Line 1: i starts at m minus 1, the index of the last real value in nums1. With m = 3 that is index 2, which holds the 3.
• Line 2: j starts at n minus 1, the last value in nums2. With n = 3 that is index 2, which holds the 6.
• Line 3: k starts at m plus n minus 1, the very last slot in nums1. With m = 3 and n = 3 that is index 5, the final empty spot.
• Line 4: the loop runs while j is still zero or higher. That means nums2 still has values left to place.
• Line 5: we check two things at once. Is i still valid, and is nums1[i] bigger than nums2[j]? Both must be true to take from nums1.
• Line 6: if so, we copy nums1[i] into slot k, then step both i and k backward. The minus minus uses the value, then moves the pointer left.
• Lines 7 to 8: otherwise, nums2[j] is the bigger or equal value. So we drop it at k. Then we step both j and k backward.

The trick is direction. We place the biggest remaining value at the back first. Then we work our way toward the front. The free space sits at the back of nums1. So slot k never lands on a value we still need to read.

6.2 Java Code

public class MergeSortedArrayThreePointer {
    public static void merge(int[] nums1, int m,
                             int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
 
    public static void main(String[] args) {
        int[] nums1 = { 1, 2, 3, 0, 0, 0 };
        int[] nums2 = { 2, 5, 6 };
        merge(nums1, 3, nums2, 3);
        System.out.println(java.util.Arrays.toString(nums1));
        // [1, 2, 2, 3, 5, 6]
    }
}

6.3 Reading the Code Line by Line

The Java mirrors the pseudocode closely. Here is what each part does in the running code.

• The three setup lines place the pointers at the back. Here i = m – 1 lands on the last real value of nums1. Next, j = n – 1 lands on the last value of nums2. Finally k = m + n – 1 lands on the final slot of nums1.
• while (j >= 0) keeps going until every value from nums2 has been placed. We watch j, not k, on purpose.
• if (i >= 0 && nums1[i] > nums2[j]) asks two things. Does nums1 still have values? And is its current value the bigger one? The i >= 0 part must come first. That way we never read nums1 at a negative index.
• nums1[k–] = nums1[i–] copies the nums1 value into slot k, then moves k and i one step left. The else branch does the same with nums2 and j.

Why watch j and not k? Once nums2 is empty, the values still in nums1 are already sorted. They are also already sitting in the correct front slots. So there is nothing left to do, and we stop early.

And why the i >= 0 guard? Sometimes nums1 runs out of real values first. Then i drops below zero. The guard makes the check fail. So we fall into the else branch instead. From there we keep pouring the rest of nums2 into the front slots. That one small guard handles the tricky edge cases for free.

7. Dry Run of the Three-Pointer Approach

Watching the code run by hand makes it stick. Let us trace nums1 = [1, 2, 3, 0, 0, 0] with m = 3, and nums2 = [2, 5, 6] with n = 3. We start with i = 2, j = 2, and k = 5. Read each row as one turn of the loop, and watch the three pointers slide left.

Now let us walk through each turn slowly, following where every pointer moves.

• Step 1: we compare nums1[2] = 3 with nums2[2] = 6. Since 6 is bigger, it drops into slot k = 5. Then j slides to 1 and k slides to 4. i stays at 2, because we took from nums2.
• Step 2: nums1[2] = 3 meets nums2[1] = 5. Again nums2 wins, so 5 goes into slot 4. Now j slides to 0 and k slides to 3.
• Step 3: nums1[2] = 3 meets nums2[0] = 2. This time nums1 is bigger, so 3 drops into slot 3. Here i slides to 1 and k slides to 2. Notice the 3 barely moved, from index 2 to index 3.
• Step 4: nums1[1] = 2 meets nums2[0] = 2. It is a tie, and our else branch takes from nums2. So 2 goes into slot 2, then j slides to minus 1.
• Step 5: j is now below zero, so the while loop stops. We do not touch the front of nums1 at all.

Look at step five closely. Once j drops below zero, nums2 is empty. The values 1 and 2 at the front of nums1 never moved, because they were already in their correct spots. So we stop early, and the array is done as [1, 2, 2, 3, 5, 6].

7.1 The Same Dry Run on Paper

The sketch above shows the same trace. The two arrays sit on top, and each step shows the bigger value dropping into the back slot. Many people find this picture easier than the table, so use whichever clicks for you.

8. Comparing the Three Approaches

All three approaches give the correct answer. They just pay different prices. Here is the plain comparison.

In an interview, mention dump and sort first to show you understand the problem. Then bring up the copy merge to show you can use the sorted order. Finally reach for the three-pointer trick to show the best answer with no extra space. That path from blunt to elegant is exactly what interviewers want to see.

9. Common Mistakes and Edge Cases

A few small traps catch beginners on this problem. Keep these in mind.

• Do not treat the trailing zeros in nums1 as real data. They are just empty room.
• In the three-pointer version, always guard with i >= 0 before reading nums1[i]. Skipping this can crash on the front edge.
• When n is zero, nums2 is empty and nums1 is already correct. All approaches handle this naturally.
• When m is zero, nums1 has no real values, so you simply copy nums2 in. The three-pointer loop does this on its own.
• Watch the tie case. When both values are equal, either choice keeps the order sorted, so do not overthink it.

10. Conclusion

The Merge Sorted Array problem DSA looks like a warm-up, and it is. But the fill-from-the-back idea inside it is a real skill. You will reuse that same trick in merge sort, in linked list merges, and in many two-pointer problems.

So take the lesson, not just the answer. Try dump and sort first to be safe. Reach for the copy merge when you want linear time and clarity. Then use the three-pointer trick when you want the fastest in-place answer. Once that pattern feels natural, a whole family of merge problems opens up for you.

11. What’s Next

You now have Merge Sorted Array in your toolkit, so let us keep the momentum going. Here is where you came from and where you head next in this series.

• Previous: Move Zeroes in Java — push every non-zero to the front and park the zeros at the end in one pass.
• Next up: Valid Palindrome — use two pointers from both ends to check a string reads the same both ways.

12. Further Reading

• LeetCode Merge Sorted Array problem — practice the original problem and test your solution.
• Oracle Java Arrays documentation — the official reference for Arrays.sort and Arrays.copyOf used here.

javahandson.com | DSA Series | Arrays & Strings