jeffgerickson
[Oops.] May be there is a error in Page 28
Please verify that the error is present in the most recent revision before reporting. 1st edition
Chapter number or note title: [title] 1.4 mergesort Correctness
Page number: [page] Page 28
Error description: [error]
First paragraph at Page 28
Proof: Let A[1 .. n] be any array and m any integer such that the subarrays A[1 .. m] and A[m + 1 .. n] are sorted. We prove that for all k from 0 to n, the last n − k − 1 iterations of the main loop correctly merge A[i .. m] and A[ j .. n] into B[k .. n]. The proof proceeds by induction on n − k + 1, the number of elements remaining to be merged.
I think "We prove that for all k from 0 to n, the last n − k − 1 iterations of the main loop correctly" has a error: We prove that for all k from 0 to n, assumed that k is 0 and n is 0, so n - k - 1 is -1( -1 ?)
In my opinion It should be k is 0 and n is 0, so n - k + 1 is 1. Suggested fix (if any): [fix]
Suggested fix:
change
"We prove that for all k from 0 to n, the last n − k − 1 iterations of the main"
to
"We prove that for all k from 0 to n, the last n − k + 1 iterations of the main"
