Linear-time Merging

The remaining piece of merge sort is the merge function, which merges two adjacent sorted subarrays, $array[p \cdots q]$ and $array[q+1 \cdots r]$ into a single sorted subarray in $array[p \cdots r]$. We’ll see how to construct this function so that it’s as efficient as possible. Let’s say that the two subarrays have a total of $n$ elements. We have to examine each of the elements in order to merge them together, and so the best we can hope for would be a merging time of $\Theta(n)$. Indeed, we’ll see how to merge a total of $n$ elements in $\Theta(n)$ time.

In order to merge the sorted subarrays $array[p \cdots q]$ and $array[q+1 \cdots r]$ and have the result in $array[p\cdots r]$ ...