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:

StepDetailsRuntime
IMake a list, $C$, large enough to hold all elements of $A$ & $B$$O(1)^{*}$
IICopy elements of $A$ to $C$$O(n)$
IIICopy elements of $B$ to $C$$O(m)$
VISort $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.

Linear-time merge