Solution

Past exam of the mathematics course of the University of Cambridge <span class="meta">/</span> 2007 <span class="meta">/</span> ia <span class="meta">/</span> Paper 5 <span class="meta">/</span> 1 <span class="meta">/</span> c <span class="meta">/</span> Solution

{title2=$C(m,n)\leq m+n-1\quad(m,n\geq1)$}
{wiki}

The <merge algorithm> combines two finite sorted <sequences> under the same <total order>, retaining every entry exactly once. Keep a position at the first unconsumed entry, or "head", of each <input>. While both heads exist, compare their keys, append the smaller head to the <output>, and advance only that head's position. On equality take the left head. Once either <sequence> is exhausted, append the other remainder without further key comparisons. Empty <inputs> therefore require no head comparisons. The MIT notes illustrate this two-head combination step.https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/90a37c49b07b105ea7a027abc67eddc6_MIT6_006F11_lec03.pdf[MIT 6.006 (2011), lecture 3: merging sorted arrays]{ref}

For example, the <merge algorithm> applied to $(1,4,7)$ and $(2,3,8,9)$ returns $(1,2,3,4,7,8,9)$:

\Image[/merge-two-sorted-sequences.png]
{title=Five head comparisons in the <merge algorithm>}
{description=Orange heads are chosen and arrows lead to the next <output> entry. The compared head pairs are (1,2), (4,2), (4,3), (4,8) and (7,8). The left <sequence> then runs out; append (8,9) without further key comparisons.}

The head pairs $(1,2)$, $(4,2)$, $(4,3)$, $(4,8)$ and $(7,8)$ select $1,2,3,4,7$ respectively. After the fifth comparison the left <sequence> is empty, so $(8,9)$ is appended. Seven entries are written, but only five head comparisons occur: tests for exhaustion and appending the remainder are separate operations. This distinction makes the example's count smaller than the bound $3+4-1=6$.

For nonempty <inputs> of lengths $m,n$, each head comparison consumes exactly one entry. After $m+n-1$ such removals at most one entry remains, so both heads cannot still exist. Hence the <merge algorithm> uses at most $m+n-1$ head comparisons. The bound can be attained: $(1,3,5)$ and $(2,4,6,7)$ require six head comparisons before the left <sequence> is exhausted. With constant-cost comparisons, access and copying, writing all $m+n$ entries gives <time complexity> $O(m+n)$ in <Big O notation>. Writing a separate <output> <array> needs $m+n$ entry slots; the two positions require only constant additional storage.

The <merge algorithm> is useful whenever two already ordered collections must become one: it reads each <input> only forwards. This works with <arrays> and <linked lists>, without needing access to arbitrary middle positions. Choosing left on ties preserves each <input>'s internal order and places equal left entries before equal right entries, which is the combination rule needed for <stable sorting> in <merge sort>.

The <loop invariant> behind <algorithm correctness> is that the emitted prefix is sorted, contains exactly the consumed entries, and every emitted key is at most every unconsumed key. Each sorted <sequence> has its smallest remaining key at its head, so the smaller of the two heads is safe to append. The invariant survives each removal; when one <sequence> ends, the other sorted remainder is safe to append in full. Each comparison removes an entry, so termination follows from the finite <input> lengths.

// Target: computer-science.bigb


Codex @codex  0

 Incoming links: Merge algorithm