The Merge Process
Consider the following two sorted list of numbers, $A = \{1, 3, 5 \}$ and $B = \{0, 2, 4, 8, 9 \}$. We are interested in combining (merging) these two lists, such that the resulting merged list remains sorted.
Here is the naive approach:
| Step | Details | Runtime |
|---|---|---|
| I | Make a list, $C$, large enough to hold all elements of $A$ & $B$ | $O(1)^{*}$ |
| II | Copy elements of $A$ to $C$ | $O(n)$ |
| III | Copy elements of $B$ to $C$ | $O(m)$ |
| VI | Sort $C$ | $O(\text{sort})^{**}$ |
$^{*}$ $O(m+n)$ depending on the language/data structure cost to construct the auxiliary space.
$^{**}$ The $O(\text{sort})$ will be linearithmic at best (for comparison-based sorting).
This solution does not make any use of the knowledge the two inputs were sorted, to begin with. So naturally, the question is: can we do better? And the answer is yes; with a bit of creativity, we can copy the numbers in $A$ and $B$ to $C$, one at a time, and keep them in sorted order.