13. Merge Two Sorted Arrays (Combined Sorted Output)

Given two already-sorted arrays, print a single line containing every element from both arrays, in sorted order.

Input: The first line contains n1 followed by a line with n1 space-separated sorted integers. The next line contains n2 followed by a line with n2 space-separated sorted integers. Output: Print a single line containing every element from both arrays, in sorted order.

0 <= n1, n2 <= 10^5

Once one array runs out, the remaining elements of the OTHER array can be appended directly without further comparison - they're already sorted and all guaranteed to be at least as large as everything already placed.

Given two arrays that are each already sorted, combine them into one single sorted list. Brute force: Combine both arrays into one list and run a general-purpose sort on the whole thing - this works but costs O((n1+n2) log(n1+n2)), ignoring the fact that both halves are ALREADY sorted. Optimised: Since both arrays are already individually sorted, a single two-pointer merge (exactly the 'merge' half of merge sort) combines them in linear time - there's no need to re-sort information you already have in sorted order.

Walk both arrays simultaneously with pointers i and j starting at 0. At each step, compare arr1[i] and arr2[j], append the smaller one to the output, and advance only that pointer; once either pointer runs off the end of its array, append the entire remainder of the other array unchanged. Because each element is examined exactly once and only a constant amount of bookkeeping (the two pointers) is needed, this is the classic linear-time merge step from merge sort, with no heap or sorting overhead at all. Time: O(n1+n2) Space: O(1)

Push the first element of each array onto a min-heap tagged with which array it came from. Repeatedly pop the smallest element, append it to the output, and push the next not-yet-used element from that same array (if any remain) back onto the heap; stop once the heap is empty. This exploits the sortedness of both inputs like the optimal approach does, but routes the comparisons through a heap - a technique that generalizes directly to merging more than two sorted arrays at once - at the cost of a small logarithmic overhead per element from heap maintenance. Time: O((n1+n2) log 2) Space: O(1)

Simply append every element of the second array onto a copy of the first array, then run a general-purpose comparison sort over the combined array and print it. This is correct regardless of how the two arrays relate to each other, but it completely ignores the fact that both inputs are already individually sorted, paying a logarithmic sorting factor for information that's actually free to exploit. Time: O((n1+n2) log(n1+n2)) Space: O(n1+n2)

1. Keep a pointer into each of the two arrays, both starting at the beginning. 2. Compare the two pointers' current values, and append the SMALLER one to the result, advancing that pointer. 3. Repeat until one array is exhausted, then append whatever remains of the other array directly (since it's already sorted).

Time: O(n1 + n2) - each element from both arrays is visited and placed exactly once. Space: O(n1 + n2), for the combined result array.

n1 = 0 or n2 = 0 (one array is empty, output is just the other array); n1 = n2 = 0 (an empty output line); and n1 or n2 at the largest size 10^5 (confirming the two-pointer merge is O(n1+n2)).

This exact two-pointer merge step is the beating heart of merge sort itself - recognizing and naming that connection shows you understand WHY merge sort's merge step is efficient, not just that it exists.