This proof is a proof by induction, and goes as follows:
P(n) is the assertion that "Quicksort correctly sorts every input array of length n."
Base case: every input array of length 1 is already sorted (P(1) holds)
Inductive step: fix n => 2. Fix some input array of length n.
Need to show: if P(k) holds for all k < n, then P(n) holds as well
He then draws an array A partitioned around some pivot p. So he draws p, and calls the part of the array that is < p as the 1st part, and the part that is > p is the second part. The length of part 1 = k1, and the length of part 2 is k2. By the correctness proof of the Partition subroutine (proved earlier), the pivot p winds up in the correct position.
By inductive hypothesis: 1st, 2nd parts get sorted correctly by recursive calls. (Using P(K1),P(k2))
So: after recursive calls, entire array is correctly sorted.
My confusion: I have a lot of problem seeing exactly how this proves the correctness of it. So we assume that P(k) does indeed hold for all natural numbers k < n.
Most of the induction proofs I had seen so far go something like: Prove base case, and show that P(n) => P(n+1). They usually also involved some sort of algebraic manipulation. This proof seems very different, and I don't understand how to apply the concept of Induction to it. I can somewhat reason that the correctness of the Partition subroutine is the key. So is the reasoning for its correctness as follows: We know that each recursive call, it will partition the array around a pivot. This pivot will then be in its rightful position. Then each subarray will be further partitioned around a pivot, and that pivot will then be in its rightful position. This goes on and on until you get an subarray of length 1, which is trivially sorted.
But then we're not assuming that P(k) holds for all k < n....we are actually SHOWING it does (since the Partition subroutine will always place one element in its rightful position.) Are we not assuming that P(k) holds for all k