Merge Sorted Array in Java DSA: From an Extra Array to the Backward Sweep

Learn Merge Sorted Array in Java DSA with three approaches, full step-by-step dry runs, and the in-place backward two-pointer solution interviewers want.

1. Introduction

Merge Sorted Array in Java is one of those problems that looks tiny but hides a neat trick. You get two sorted arrays. Your job is to blend them into one sorted array.

Here is the twist that trips people up. The first array already has empty room at its end, and you must do the merge inside that same array. No brand new array is allowed in the best solution.

We build the answer in three steps, like always. A simple version merges into a fresh array and copies back. A lazier version dumps everything together and sorts. The final one walks two pointers from the back and needs no extra space at all.

Every approach comes with a full, step-by-step dry run on the same seven numbers. Nothing is skipped, so you can follow exactly what each line does and what changes at every step.

2. Understanding the Problem

Let us pin down the rules before touching code.

• You get two sorted arrays, nums1 and nums2.
• nums1 is longer than it needs to be. Its first m slots hold real values, and the last n slots are zeros left as blank space.
• nums2 holds n real values.
• You must merge nums2 into nums1 so nums1 ends up fully sorted.

Take nums1 = [1, 3, 5, 7, 0, 0, 0] with m = 4, and nums2 = [2, 4, 6] with n = 3. The four real numbers are 1, 3, 5, 7. The three zeros are just parking space. After merging, nums1 should read [1, 2, 3, 4, 5, 6, 7].

The zeros matter. They are not part of the data, so treat them as free room you are allowed to overwrite.

3. Concepts You Need Here

3.1 Both Inputs Are Already Sorted

This is the gift the problem hands you. Because both arrays climb in order, you never have to sort from scratch. You only have to pick the right next value at each step.

• The smallest unused value is always at the front of one array or the other.
• The largest unused value is always at the back of one array or the other.

3.2 The Two-Pointer Idea, Running Backward

Two pointers usually crawl inward from both ends. Here we do something different. We fill nums1 from its last slot toward its first, and we compare the biggest leftover values.

• One pointer sits on the last real value of nums1.
• Another pointer sits on the last value of nums2.
• A third pointer marks the slot we are writing into, starting at the very end of nums1.

Filling from the back is the key move. The empty room lives at the end of nums1, so writing there never stomps on a value we still need to read.

4. Approach 1: Merge Into a New Array

Build a fresh array of size m plus n. Walk both inputs from the front, always copying the smaller current value. Then copy the finished array back into nums1. It wastes memory, but it makes the merge logic crystal clear.

4.1 Pseudocode

merged = new array of size m + n
i = 0            // pointer into nums1's real part
j = 0            // pointer into nums2
k = 0            // pointer into merged
 
while i < m and j < n:
    if nums1[i] <= nums2[j]:
        merged[k] = nums1[i]; i = i + 1
    else:
        merged[k] = nums2[j]; j = j + 1
    k = k + 1
 
while i < m:  merged[k++] = nums1[i++]   // drain nums1
while j < n:  merged[k++] = nums2[j++]   // drain nums2
 
copy merged back into nums1

4.2 Pseudocode Explained

The whole idea rests on three pointers. Read each one as a finger resting on an array. Here finger i walks the real part of nums1, finger j walks nums2, and finger k marks the next open slot in the new merged array.

The main while loop is the heart of the merge. It keeps running only while both inputs still have numbers left, because a merge needs two things to compare. At each turn we look at the two values under i and j, copy the smaller one into merged, and step that finger forward. Its k partner moves forward too, since one more slot is now filled.

• Comparing front values works because both arrays are sorted, so the smallest unused number is always at one of the two fronts.
• Using <= rather than < only decides the order of equal values, which keeps the merge stable but does not change correctness here.

Two drain loops then handle the leftover tail. When one input empties, the other may still hold larger values, and those are already sorted among themselves. So one drain loop simply pours the rest straight into merged, with no comparing needed.

A final copy step exists only because of the problem’s rule. Our answer sits in merged, but the problem wants it inside nums1, so we copy every value back over. That last copy is exactly the wasteful part we remove later.

4.3 Java Code

public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int[] merged = new int[m + n];
    int i = 0, j = 0, k = 0;
 
    while (i < m && j < n) {
        if (nums1[i] <= nums2[j]) {
            merged[k++] = nums1[i++];
        } else {
            merged[k++] = nums2[j++];
        }
    }
    while (i < m) merged[k++] = nums1[i++];
    while (j < n) merged[k++] = nums2[j++];
 
    for (int t = 0; t < m + n; t++) nums1[t] = merged[t];
}

4.4 Java Code Explained

• Line 2makes a fresh array with room for every value.
• Then line 3 sets the three pointers i, j and k to zero.
• Lines 5 to 11compare the two current values and copy the smaller one into merged.
• The two lines 12 to 13drain whichever input still has numbers left.
• Finally line 15 copies merged back into nums1, so the answer lands where the problem wants it.

4.5 Dry Run of the New-Array Merge

Inputs: nums1 = [1, 3, 5, 7, 0, 0, 0], m = 4, and nums2 = [2, 4, 6], n = 3. We trace every write into merged, so nothing is hidden. Watch the merged array grow on the right.

4.6 Reading the Dry Run

Let us walk the whole trace step by step and see how the smaller value keeps winning at every turn.

Steps 1 to 6: both inputs still have numbers.

This is the main loop, where the real comparing happens. Each step lines up the current nums1 value against the current nums2 value, copies the smaller one, and slides only that finger forward. The other finger stays put, ready to be compared again next time.

• Step 1: i on 1, j on 2. Since 1 ≤ 2, the 1 is smaller, so we copy it and move i to index 1. merged is [1]. Notice j did not move, because 2 has not been used yet.
• Then step 2: i on 3, j on 2. Now 3 > 2, so the 2 wins and we move j to index 1. merged is [1, 2]. This time i stayed on the 3, which is still waiting.
• Next step 3: i on 3, j on 4. Since 3 ≤ 4, the 3 goes in and i moves to index 2. merged is [1, 2, 3]. The pattern is clear now: whoever loses keeps their finger parked.
• At step 4: i on 5, j on 4. Now 5 > 4, so the 4 wins and j moves to index 2. merged is [1, 2, 3, 4].
• By step 5: i on 5, j on 6. Since 5 ≤ 6, the 5 goes in and i moves to index 3. merged is [1, 2, 3, 4, 5]. Only the 7 is left in nums1 now.
• Finally step 6: i on 7, j on 6. Now 7 > 6, so the 6 wins and j moves to index 3, which is off the end of nums2. merged is [1, 2, 3, 4, 5, 6], and nums2 is fully used up.

See how the two fingers never rush ahead of each other. Each step advances exactly one of them, so no value is ever skipped or copied twice.

Step 7: nums2 is empty, so we drain nums1.

With j now past the end of nums2, the compare in the while loop can no longer run, so the main loop stops. One number is still unused, the 7 sitting at index 3 of nums1.

• The first drain loop copies that 7 straight into merged, giving [1, 2, 3, 4, 5, 6, 7]. No comparing is needed, because the 7 is the only value left and it is already the largest.
• The second drain loop, the one for nums2, has nothing to do. nums2 emptied back at step 6, so its loop condition is false right away.

Now merged holds the full sorted result, but it is the wrong array. The final line copies merged back into nums1, value by value. After that, nums1 reads [1, 2, 3, 4, 5, 6, 7], exactly the answer we wanted. We did pay for a whole extra array to get there, though.

4.7 Time and Space Cost

• Time is O(m + n), because each value is copied a constant number of times.
• Space is O(m + n), because of the whole extra merged array.

The logic is easy to trust, but that extra array is the weak spot. The problem practically dares you to remove it, which we do soon.

5. Approach 2: Dump Everything and Sort

Here is the lazy shortcut. Copy nums2 into the empty tail of nums1, then sort the whole thing. It is short to write, but it throws away the fact that both inputs were already sorted.

5.1 Pseudocode

for k from 0 to n-1:
    nums1[m + k] = nums2[k]   // fill the empty tail
 
sort nums1                    // sort the full array

5.2 Pseudocode Explained

This approach trades cleverness for plain simplicity, and it works in two clear stages.

The first loop fills the empty tail. Each value of nums2 drops into the zero slots of nums1, one after another, starting at index m. The index m + k is what lines them up, since the real values already occupy slots 0 to m minus 1. After this loop, nums1 holds all m plus n real values, but the ones from nums2 sit in a jumbled block near the end.

The sort then cleans up the mess. One call reorders the whole array so every value lands in its correct place. It does not care that parts of the array were already sorted, and that is the catch.

• Both inputs arrived sorted, yet this method throws that head start away and re-sorts everything from scratch.
• That wasted effort is exactly why a real merge, which keeps the sorted order, beats this approach on speed.

5.3 Java Code

public static void merge(int[] nums1, int m, int[] nums2, int n) {
    for (int k = 0; k < n; k++) {
        nums1[m + k] = nums2[k];
    }
    Arrays.sort(nums1);
}

5.4 Java Code Explained

• Line 2 to 4copy every value of nums2 into the blank tail of nums1.
• The index m + k lands each value just after the real part of nums1.
• Then line 5 sorts the whole array in one call, and the merge is done.

5.5 Dry Run of the Sort Approach

Inputs: nums1 = [1, 3, 5, 7, 0, 0, 0], m = 4, and nums2 = [2, 4, 6], n = 3. First we trace the copy loop, then the sort. Nothing is skipped.

Copy loop: filling the empty tail.

Sort step: one call orders everything.

5.6 Reading the Dry Run

Let us go through both stages and see exactly what each one changes in nums1.

Copy loop, steps 1 to 3.

This loop only touches the three zero slots at the end of nums1. The real values 1, 3, 5, 7 in the front are never read or moved. The index m + k, with m being 4, is what steers each value into the right blank slot.

• Step 1: k is 0, so the target is index 4 and the value is nums2[0], which is 2. The first zero turns into 2, and nums1 becomes [1, 3, 5, 7, 2, 0, 0].
• Then step 2: k is 1, so the target is index 5 and the value is nums2[1], which is 4. nums1 becomes [1, 3, 5, 7, 2, 4, 0].
• Next step 3: k is 2, so the target is index 6 and the value is nums2[2], which is 6. Every zero is now gone, and nums1 becomes [1, 3, 5, 7, 2, 4, 6].

At this point all seven real values live in nums1, but the block 2, 4, 6 sits out of order behind the 7. The array is complete but not sorted.

Sort step.

Now one sort call reorders the whole array. It shuffles values with no memory that 1, 3, 5, 7 were already in order, and that 2, 4, 6 were too. The result is [1, 2, 3, 4, 5, 6, 7], which is correct. Still, the sort re-examined values that never needed moving. So this method does strictly more work than a plain merge would.

5.7 Time and Space Cost

• Time is O((m + n) log(m + n)), because of the full sort.
• Space is O(1) extra if the sort is in place, or O(log n) for the sort’s own stack.

Short code, slower class. Sorting from scratch is heavier than a plain merge, so interviewers rarely accept this one. The next approach fixes both the speed and the memory at once.

6. Approach 3: Backward Two-Pointer Merge

This is the answer interviewers want. Fill nums1 from its last slot backward, always placing the larger of the two current values. Because the free room sits at the end, we never overwrite a value we still need. No extra array, no full sort.

6.1 Pseudocode

p1 = m - 1          // last real value in nums1
p2 = n - 1          // last value in nums2
p  = m + n - 1      // last slot in nums1 (write position)
 
while p2 >= 0:
    if p1 >= 0 and nums1[p1] > nums2[p2]:
        nums1[p] = nums1[p1]; p1 = p1 - 1
    else:
        nums1[p] = nums2[p2]; p2 = p2 - 1
    p = p - 1

6.2 Pseudocode Explained

Three pointers again, but this time they all start at the back. Picture each one as a finger on the last item it cares about. Here p1 sits on the last real value of nums1, and p2 sits on the last value of nums2. The third finger, p, marks the slot we write into, starting at the very end of nums1.

The loop fills nums1 from right to left. At each turn we compare the two current values under p1 and p2, then write the larger one into slot p. This is the reverse of the front merge: instead of picking the smallest and filling from the front, we pick the largest and fill from the back. Whichever value we used, its own finger steps back by one, and the write finger p steps back too.

The safety of this whole scheme comes from where the empty room lives. The blank slots sit at the tail of nums1, so the first few writes land on those zeros. By the time p reaches the real values, those values have already been read and copied further right, so overwriting them is harmless.

• We loop on p2 only, not p1, because nums2 is the array being folded in.
• Once p2 falls below zero, every nums2 value is placed. Any leftover nums1 values are already sitting in their correct front slots, so no extra work is needed.
• The guard p1 >= 0 inside the compare protects against reading before the start of nums1 when nums1 empties first.

6.3 Java Code

public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1;
    int p2 = n - 1;
    int p  = m + n - 1;
 
    while (p2 >= 0) {
        if (p1 >= 0 && nums1[p1] > nums2[p2]) {
            nums1[p--] = nums1[p1--];
        } else {
            nums1[p--] = nums2[p2--];
        }
    }
}

6.4 Java Code Explained

• Lines 2 to 4set the three back pointers p1, p2 and p.
• Line 6 loops while nums2 still has a value to place.
• Line 7checks p1 first, so we never read past the front of nums1.
• When nums1’s value is larger, line 8 writes it and steps both p and p1 back.
• Otherwise line 10 writes the nums2 value and steps both p and p2 back.
• No drain loop for nums1 is needed, since its remaining values already sit in place.

6.5 Dry Run of the Backward Merge

Inputs: nums1 = [1, 3, 5, 7, 0, 0, 0], m = 4, and nums2 = [2, 4, 6], n = 3. So p1 starts at 3, p2 at 2, and p at 6. We trace every write, showing the full nums1 array after each one.

Legend: p1 is the read finger on nums1, p2 is the read finger on nums2, and p is the write finger moving backward through nums1.

6.6 Reading the Dry Run

This is the trace that matters most, so let us go slowly. At every step we compare the two biggest leftovers, drop the winner into the far right open slot, and step that finger back. Keep one eye on which slot gets overwritten, because that is where the in-place magic hides.

Step 1: 7 beats 6.

The two biggest leftovers are nums1[3] = 7 and nums2[2] = 6. Since 7 > 6, the 7 is the largest value in the entire merge, so its home is the very last slot, index 6.

• We write 7 into index 6, then step p1 back to index 2 and p back to index 5.
• The slot we filled held a 0, pure blank space, so no real value was lost. nums1 is now [1, 3, 5, 7, 0, 0, 7].
• The original 7 still sits at index 3 too, but that copy no longer matters, since p1 has already moved past it.

Step 2: 6 beats 5.

Now p1 is on 5 and p2 is still on 6. Since 5 ≤ 6, the else branch runs and the 6 from nums2 takes the next slot. The 6 is the largest of the values still waiting.

• We write 6 into index 5, then step p2 back to index 1 and p back to index 4.
• Index 5 also held a 0, so again we filled only junk. nums1 is now [1, 3, 5, 7, 0, 6, 7].

Step 3: 5 beats 4.

Here p1 is on 5 and p2 is on 4. Since 5 > 4, the 5 from nums1 wins this round.

• We write 5 into index 4, then step p1 back to index 1 and p back to index 3.
• This time we overwrote index 4, which was the last remaining 0. From here on, every write lands on a slot that once held a real value.
• That is safe because the value at index 4 was already blank, and the 5 we copied came from index 2, which p1 has already left. nums1 is now [1, 3, 5, 7, 5, 6, 7].

Step 4: 4 beats 3.

Now p1 is on 3 and p2 is on 4. Since 3 ≤ 4, the 4 from nums2 is larger and gets placed.

• We write 4 into index 3, then step p2 back to index 0 and p back to index 2.
• Index 3 held the original 7, but that 7 was already copied to index 6 back in step 1, so overwriting it loses nothing. nums1 is now [1, 3, 5, 4, 5, 6, 7].
• Look at the right half, indices 3 through 6: it already reads 4, 5, 6, 7, fully sorted and final.

Step 5: 3 beats 2.

Here p1 is on 3 and p2 is on 2. Since 3 > 2, the 3 from nums1 wins.

• We write 3 into index 2, then step p1 back to index 0 and p back to index 1.
• The 3 came from index 1 and lands at index 2, one slot to the right. So the value it overwrites was the old 5, which we already placed earlier. nums1 is now [1, 3, 3, 4, 5, 6, 7].
• Only two values are left to place, the 1 in nums1 and the 2 in nums2.

Step 6: 2 beats 1.

Now p1 is on 1 and p2 is on 2. Since 1 ≤ 2, the 2 from nums2 is larger and drops in.

• We write 2 into index 1, then step p2 back to index -1 and p back to index 0.
• With p2 now below zero, every value from nums2 has found its home. nums1 is now [1, 2, 3, 4, 5, 6, 7].

Step 7: nums2 is empty, loop ends.

The while check p2 >= 0 is now false, so the loop stops here. Only one value was never touched, the 1 at index 0.

• That 1 was already the smallest value and already sat at the front, so leaving it alone is exactly right.
• No drain loop for nums1 is needed either, a real bonus of the backward method. Any nums1 values still unplaced are always the smallest ones, and they already sit in their correct front slots.
• The final nums1 reads [1, 2, 3, 4, 5, 6, 7], and we used no extra array at all.

Step back and notice the pattern across all seven steps. Every single write either filled a blank zero or overwrote a value we had already copied to safety. That is why one backward pass can finish the whole merge in place, with nothing but three little index variables.

6.7 Comparing the Three Traces

7. The Dry Run on Paper

Tables are exact, but a sketch often lands faster. Here is the same backward merge drawn by hand.

• Each step compares the two biggest leftovers and drops the winner into the rightmost open slot.
• The write finger p slides left with every placement, so slots fill from the back to the front.
• At the bottom, the finished array reads [1, 2, 3, 4, 5, 6, 7].

8. Comparing the Three Approaches

All three give the same sorted nums1. They just pay different prices.

The first and third share the same time class. What splits them is memory. The backward sweep carries only three little indices, while the new-array version drags a full copy along.

In an interview, start with the new-array merge, point out the wasted space, then flip to the backward sweep and explain why filling from the end is safe. That climb is the story interviewers want to hear.

9. Common Mistakes and Edge Cases

A few small traps catch beginners on Merge Sorted Array. Keep them in mind.

• Merging forward into nums1 overwrites values you still need to read, which corrupts the result.
• Forgetting the p1 >= 0 guard can read past the front of nums1 and crash.
• When n is 0, nums2 is empty, so nums1 is already the answer and nothing should change.
• When m is 0, every real value lives in nums2, so the loop simply copies all of nums2 across.
• Mixing up m plus n for the write start slot puts the first value in the wrong place.

Run the m = 0 and n = 0 cases through your code before you call it done. They catch more bugs than any ordinary input will.

10. Interview Questions

11. Conclusion

Merge Sorted Array in Java looks harmless, yet the in-place rule quietly raises the bar. The trick is to stop fighting the empty space and start using it.

Our seven-number trace made the payoff clear. The new-array merge copied everything twice. The backward sweep filled nums1 from the end and finished in one clean pass, with no extra array at all.

So take the pattern, not just the answer. When free room sits at one end, fill from that end. Compare the biggest leftovers, drop the winner in, and let the pointers walk back. That habit will serve you on many array problems waiting further down the list.

12. Further Reading

• LeetCode Merge Sorted Array problem — practice the original problem and submit your own solution.
• Oracle Java Arrays documentation — the official reference for Arrays.sort and other helpers used here.
• Previous in this series: Move Zeroes in Java — shift all zeros to the end while keeping the order with two pointers.
• Next in this series: Valid Palindrome in Java — check a string from both ends using the two-pointer sweep.

javahandson.com | DSA Series | Arrays & Strings