So with those three things pasted together, we have a sorted version of the input array and since this array was an arbitrary one, of link N. That establishes the assertion P of N and since n was arbitrary, that establishes the inductive and completes the proof of correctness of quick sort for an arbitrary method of choosing the pivot element. 