The test in line 1 of the procedure reads “if ” rather than “if .“ If MERGE_SROT is called with , then the subarray is empty.
Argue that as long as the initial call of has , the test “if ” suffices to ensure that no recursive call has .
We can proof this using induction:
Base Case:
The initial call is
where , ,
Recursive step:
Assuming a recursive call is made with p ≤ r. Then:
- Compute
The two recursive calls:
1.
- Since , then
- So, ( and not )
2.
- only if
- Since , then
Therefore in all of the recursive calls
So, can never happen if is only called when