Merge two sorted arrays.

Two sorted arrays are like two neat lines at a coffee counter — the smart move is to compare the people at the front, not rebuild the whole line from scratch.

Question: How do I merge two sorted arrays in Java?

Answer: Use two pointers, one for each array. Compare the current values, copy the smaller one into a new result array, and move that pointer forward. When one array finishes, copy the remaining tail from the other array, because it is already sorted.

Interview-Ready Answer: I’d merge them with two pointers in a single pass. At each step, I compare the current elements, write the smaller one into the result, and advance that pointer; once one array is exhausted, I copy the remaining tail from the other array. That gives me O(m + n) time and O(m + n) extra space, which is better than sorting the combined array again.

What the idea is

Because both inputs are already sorted, you do not need a full sort. A pointer is just an index that tells you where you are in an array. The key mental model is: the smallest remaining item must be at one of the two fronts.

How it works under the hood

1. Start with three indexes: i for the first array, j for the second array, and k for the result array.
2. Compare a[i] and b[j].
3. Copy the smaller value into result[k].
4. Advance the pointer you used, and also advance k.
5. Repeat until one array is finished.
6. Copy the leftover tail from the other array. You can do this because the leftover elements are already in sorted order.

If you want the merge to be stable, which means equal values keep their original relative order, use <= and take from the left array first when values are equal.

Why interviewers like this approach

It shows you can exploit structure. A sorted array gives you a strong clue: every comparison should eliminate one candidate forever. That is much faster than concatenating both arrays and calling a general sort.

Performance notes

With arrays of length 50,000 and 50,000, the two-pointer method does at most 100,000 writes and about 99,999 comparisons. A full re-sort would do far more work, roughly proportional to 100,000 × log2(100,000), which is around 1.7 million comparison-level steps. That difference is very visible in interviews and in real systems.

Edge cases and gotchas

• Empty arrays: If one input is empty, the answer is just the other array.
• Duplicate values: Keep duplicates; the merge should not drop them.
• Negative numbers: No special handling is needed if the arrays are still sorted.
• Null arrays: Decide whether to reject them or treat them as invalid input; be explicit.
• Not actually sorted: The algorithm fails silently and returns a wrong order, which is a classic interview trap.

When to use it: Use this whenever both inputs are already sorted and you want a sorted combined result. If the first array has extra capacity, an in-place backward merge is a nice follow-up variant: fill from the end to avoid overwriting values you have not read yet.

Real-World Story: In a checkout service, one team merged two sorted lists of line items: one from the cart and one from a pricing engine that had already ranked discounts by priority. The merge kept the page rendering fast because it avoided a full re-sort on every request.

What goes wrong when someone misunderstands the merge? A common bug is advancing the wrong pointer or forgetting to copy the leftover tail. In production, that shows up as missing discounts, duplicate entries, or occasional ArrayIndexOutOfBoundsException in logs. Users notice totals that do not match the cart, support tickets spike, and the team sees repeated item IDs or truncated arrays in telemetry.

The fix is usually simple: add tests for empty inputs, duplicate values, and one-side-exhausted cases. Those are the exact scenarios where a sloppy merge breaks.

Follow-up & Tricky Questions:

• Can you merge without extra space? Yes, if the first array has enough empty slots at the end. The usual trick is to fill from the back so you do not overwrite values you still need to read.
• What if the arrays are descending? Reverse the comparison logic or merge from the opposite end. The core idea is the same: compare the current extremes and move one pointer.
• How do you keep the merge stable? Use <= when comparing and choose the element from the left array first on ties. That preserves the original order of equal items from that array.
• What if one array is much longer than the other? The algorithm still stays linear. The shorter array just finishes earlier, and then you copy the rest of the longer one.
• What changes if the inputs are not sorted? Two pointers no longer work correctly. You would need to sort first or use a different data structure.
• Is concatenating and sorting ever acceptable? Yes, for tiny inputs or when readability matters more than performance. But in an interview, the sorted-input property is the clue that you should do better.
• Does the merged output itself count as extra space? Usually yes. If the interviewer asks for truly in-place behavior, they mean writing into an already allocated buffer, not pretending the output array does not exist.

Tricky / Gotcha Questions:

• Do you need to compare every remaining element after one array is exhausted? No. The remaining part is already sorted, so you can copy it directly.
• Should equal elements always come from the second array? No. That is a choice, and taking from the first array on ties is the usual stable option.
• Can you use the same algorithm on linked lists? Yes, the logic is similar, but pointer movement is through nodes instead of indexes.

Common Mistakes:

• Forgetting the tail copy: After one array ends, many candidates stop too early. Fix: copy the remaining elements from the other array in a final loop.
• Using a full sort instead of merging: This ignores the fact that the inputs are already sorted. Fix: use two pointers for linear time.
• Off-by-one errors: People often write <= or increment the wrong pointer at the wrong time. Fix: update the pointer only for the array you just copied from.
• Assuming sorted means non-empty: Empty arrays are still valid sorted arrays. Fix: test 0-length cases explicitly.

Memory Hook: “Two fingers on two zipper tracks.” Look at the two front teeth, zip the smaller one into the result, and keep going until one side runs out.

Cheat Sheet:

• Two sorted arrays + two pointers = linear merge.
• Compare the current heads, copy the smaller one, advance that index.
• When one side ends, copy the rest of the other side.
• Time: O(m+n); space: O(m+n) for a new output array.
• Use <= for stability on equal values.
• If the first array has buffer space, you can merge backward in place.

Practice Tasks:

• Merge two ascending arrays and print the result.
• Modify the code to handle descending arrays.
• Write the in-place backward merge version for an array with extra capacity.