❓ Question
The test in line 1 of the $MERGE-SORT$ procedure reads “if $p ≥ r$” rather than “if $p ≠ r$.“ If MERGE_SROT is called with $p > r$, then the subarray $A[p:r]$ is empty.
Argue that as long as the initial call of $MERGE-SORT(A, 1, n)$ has $n ≥ 1$, the test “if $p ≠ r$” suffices to ensure that no recursive call has $p > r$.
💡 Answer
💡 We can prove this using induction:
Base Case: The initial call is $MERGE-SORT(A, 1, n)$ where $n > 1$, $p = 1$, $r = n$ $\therefore$ $p ≤ r$
Recursive step: Assuming a recursive call is made with p ≤ r. Then:
- Compute $q = \lfloor(p+r)/2\rfloor$
The two recursive calls:
- $MERGE-SORT(A, p, q)$
- Since $q = \lfloor(p+r)/2\rfloor$, then $p ≤ q ≤ r$
- So, $p ≤ q$ ( and not $p > q$)
- $MERGE-SORT(A, q+1, r)$
- $q + 1 ≤ r$ only if $q < r$
- Since $q = \lfloor(p+r)/2\rfloor$, then $q ≤ r - 1$ $\equiv$ $q + 1 ≤ r$
Therefore in all of the recursive calls
$q + 1 ≤ r$ $\equiv$ $p ≤ r$
So, $p > r$ can never happen if $MERGE-SORT$ is only called when $p ≠ r$