Cannot reason with Cormen (4th ed) problem on Merge-Sort-CodePudding

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)

CodePudding user response：

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.