Proof of QuickSort algorithm correctness

Question

Recently I’ve studied QuickSort and understood its general idea.

Basically, we do the following:

1. Pick an element from the array (no matter which one and how in this context)
2. Rearrange elements in the array so that elements less than the pivot are placed prior to it (in the left part of the array), and ones that are greater than the pivot are placed after it (in the right part).
3. Apply these procedures to the left and right parts of the array.

Everything looks quite clear, but my question is: why does it eventually sorts the entire array?

I’ve read lots of articles about the QuickSort, but none of them provides a clear proof that algorithm does really work in a way they describe. So I’m looking for such a proof.

I realize that:

• Array of one element (i.e with length 1) is already sorted.
• After any partition the pivot is placed on it’s final position.

So what’s the proof of the fact that after applying QuickSort procedure to a given array of length N its elements will be ordered after a procedure completes?

P.S. I’ve seen several proofs based on mathematical induction. Unfortunately, I’m not familiar with it yet, so I’m primarily looking for non-induction proof.

Here they are:

• https://www.cs.mcgill.ca/~dprecup/courses/IntroCS/Lectures/comp250-lecture17.pdf
• Trying to understand this Quicksort Correctness proof
• https://course.ccs.neu.edu/cs5010sp17/Efficiency/quicksort5.html

Answer 1

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 <= 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.

Answer 2

I'm not sure you actually need induction (in the sense that we try to prove $P(n+1)$ assuming $P(n)$) for the quicksort proof.

Let $(a_i)_{0 \leq i \leq n}$ be your initial array. Let $(a_{q(i)})_{0 \leq i \leq n}$ be the sorted array.

In order to prove that quicksort correctly sorted the array, we have to prove that for every pair of elements $a_i$, $a_j$ such that $a_i < a_j$, we have $q(i) < q(j)$.

For that, you need to show that:

1. If $a_i < a_j$, $a_i$ and $a_j$ will eventually find themselves on different sides of a pivot (with $a_i$ to the left and $a_j$ to the right).

2. Once two elements are on different sides of a pivot, their respective order stays the same until the end of the algorithm.