Proof of QuickSort algorithm correctness
First, you need to write down your algorithm that you call "Quicksort" precisely. The devil is in the detail, and if your code doesn't get the details right, then it won't sort correctly (or you won't be able to prove that it sorts). 

And then you need to use complete induction: Take the induction statement S(N) "My algorithm will sort any subarray with n ≤ N items correctly". The more obvious statement S'(N) "My algorithm will sort any subarray with N items correctly" isn't strong enough. 

Next you prove S(1): If the array has 0 or 1 elements, does your algorithm sort it correctly? Most implementations will check that there are two or more elements as their very first step, and subarrays with 0 or 1 elements are sorted, so this should be no problem. 

Then you need to prove that S(N) implies S(N+1). If S(N) is true, then any subarray of size n ≤ N will be sorted correctly, so only the case of an array with N+1 elements needs to be handled. Here you have to prove that one Quicksort step will divide an array of N+1 into two subarrays of size ≤ N, with each element of the left subarray &lt;= each element of the right subarray, and no overlap. 

PS You will always end up with an induction proof, more or less disguised. For example: Assume there is an array that doesn’t get sorted correctly by Quicksort. If there is any array, then there must be a smallest array that doesn’t get sorted. Take that array, pick the pivot and create two sub arrays, a left one and a right one. Sort both sub arrays with Quicksort. Since they are both smaller than the smallest array that isn’t sorted correctly, they will be sorted correctly. So Quicksort works. 

That’s a property of the integers: if a set of positive integers is not empty, then it has a smallest element. Take the set of all sizes of arrays that are not correctly sorted by Quicksort. If that set is not empty, then it has a smallest element, and therefore there is a smallest array that cannot be sorted. And then you prove that the smallest array that cannot be sorted can indeed be sorted, so your assumption that some array cannot be sorted was wrong.