Question (corrected based on ERATA):
The test in line 1 of the mergeSort procedure reads if p >= r rather than if p == r.
If mergeSort is called with p > r, then the subarray A[p:r] is empty.
Argue that as long as the initial call of mergeSort(A, 1, n) has n >= 1, the test if p == r suffices to ensure that no recursive call has p > r.
Edit: The given code below should be seen as pseudo-code (not python). Array indices start from 1.
def mergeSort(arr, p, r):
if p >= r: #line 1
return #line 2
q = math.floor((p+r)/2) #line 3
mergeSort(arr, p, q) #line 4
mergeSort(arr, q+1, r) #line 5
#line 6
merge(arr, p, q, r) #line 7
My attempt at solution: For line 4, p is always less than or equal to r based on the initial conditions and the fact, that q is a midpoint between p and r. I run into problem for line 5, if I had an array with single element then line 4 is good but for line 5, q+1 leads to p > r What am I missing?
Edit: Based on comments today, it makes perfect sense to replace p>=r with p==r. there are two function calls to itself within the function. line 4 call used p and q as parameters. since q is a midpoint between p and r (with r >=p always), p can never be greater than q for line 4. for same reasons, q is always less than r and thus q+1 can only be equal to r at max. this reasoning make perfect sense and is quite apparent. i think i was just tired when i wrote this question.
if I had an array with single element then ...
then p == r and you return in line 2 and don't reach line 5.