Exercise 2.3-2
⛑️

Exercise 2.3-2

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