Confused with Cormen's (4th ed.) 2.3-2 problem. It states the following:
The test in line 1 of the Merge-Sort procedure reads "if p >= r" rather than "if p != r". If Merge-Sort 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.
Merge-Sort pseudo code:
Merge-Sort(A, p, r)
1 if p >= r
2 return
3 q = math.floor((p + r) / 2)
4 Merge-Sort(A, p, q)
5 Merge-Sort(A, q + 1, r)
6 // Merge A[p : q] and A[q + 1 : r] into A[p : r]
7 Merge(A, p, q, r)
But if we change first line condition to if p != r we'll get the following.
In case n = 1, we call Merge-Sort(A, 1, 1). Line 1 — p != r — evaluates to false. We skip line 2, q = math.floor((1 + 1) / 2) = 1 ---> q = 1. On line 4 we call Merge-Sort(A, 1, 1) and after this call returns we go to line 5 and call Merge-Sort(A, 2, 1) which is clearly a recursive call that has p > r.
What is wrong with my reasoning and how can I solve the problem?
UPD 1: @500 - Internal Server Error, thanks for replying. I should have stated that earlier — the convention of the pseudo code is that first index is 1 and last equals to array length. So in case of array of length 1 I should call Merge-Sort(A, 1, 1)
Clearly, you cannot just replace if p >= r with if p != r. p != r is the condition which should lead you to executing lines 3 through 7, so if you want to keep the same program structure, you'd need if p == r / return.
This problem with the book has already been reported and the publishers say it will be corrected in the next printing. See the official errata for the 4th edition.