The quick-sort algorithm

Quick-sort is an efficient (in-place, unstable) sorting algorithm. Although its worst-case time complexity is $O(n^{2})$, the average complexity is $O(nlog(n))$. On real-world (≈ random) inputs, quick-sort is even more efficient than other sorting algorithms with worst-case $O(nlog(n))$ time complexity like merge-sort.

I am currently reviewing my sorting algorithms and after all these years, quick-sort still baffles me. It is the less intuitive sorting algorithms that I know of. Now, there is a ton of content about the way quick-sort works and how to implement it. But this time, I wanted to prove to myself that it does work, and I had the most trouble finding a complete and rigorous correctness proof. In this post, I will formalize and gather the elements I have found here and there.

Here is the implementation we’re working with:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22



def quick_sort(array, start, end):
    '''
    Sorts input `array` between indexes `start` and `end`.
    Returns None, sorting is made in-place.
    '''
    # Base case: array of 0 or 1 elements can only be sorted
    if start >= end:
        return None
    
    # Partition input array
    l = start
    p = array[end]
    for i in range(start, end):
        if array[i] < p:
            array[l], array[i] = array[i], array[l]
            l += 1
    array[l], array[end] = array[end], array[l]

    # Recursive calls on left and right partitions
    quick_sort(array, start, l - 1)
    quick_sort(array, l + 1, end)

Note: l stand for ’left pointer’ and p stands for ‘pivot’

Why the partitioning part works

The partitioning step (lines 12-18 above) selects a pivot p, say the last element of the input array. Then, the array is rearranged as follows: [ elements < p …, p, … elements > p ]. Most likely, the partitions on ’each side’ of p are not ordered. However, p is already in ’the right place’: when the entire array will be sorted, p will be at exactly the same index.

How come the partition works? Let’s show the following invariants hold throughout the for loop:

At the beginning of each $i \in \{ start, …, end - 1 \}$,

$$ \mathcal{P} (i): \begin{cases} 1 ) \, array[k] < p \, , \, start \leq k < l_i \\[6pt] 2 ) \, array[k] \geq p \, , \, l_i \leq k < i \\ \end{cases} $$

Intuition

$\mathcal{P} (i)$ means that at the beginning of step i in the for loop:

All the elements strictly on the left of pointer l are < p
The elements on the right of pointer l (included) are ≥ p, up until index i-1

These properties are important because the mean that the array is almost partitioned as we want it to be, up to index i-1. The exception is the pivot, which stays at the end of the array throughout the loop. That is why it is swapped with array[l] after the loop is completed.

Before diving into the proof of these two statements, how can we have an intuition that they are true?

The pointer l only moves to the right after an element < p is found at step i, and put at index l. So, the elements on the left of l can only be < p.
Initially, l = i. i is incremented at each step of the for loop, while l can be incremented or not. So, l ≤ i. When does l < i? When i moves further away but not l, which happens when array[i] ≥ p. So, the elements in between l and i (if any) can only be ≥ p.

Proof

The following is not a proof by induction per say because the input array is finite. The logic is similar though: we are going to chain a (finite) number of implications together.

Base case

At the beginning of the first step of the for loop, $i = s = l_i$, so statements 1) and 2) are vacuous truths (no $k$ exists in both cases). Statement 3) is trivially true as we’ve just defined $p=array[end]$ just before entering the loop. Therefore, $\mathcal{P} (start)$.

‘Induction’

Let $i \in \{ start, …, end - 1 \}$ and assume $\mathcal{P} (i)$. Now, let’s enter inside the loop and see what happens at step $i$:

A. If $array[i] \geq p$.

Nothing happens, the pointer l is not moved to right: $l_{i+1} = l_i$.

Statement 1): We can replace $l_i$ by $l_{i+1}$ at no cost: statement 1) still holds at step $i+1$.

Statement 2): same thing, $array[k] \geq p \, , \, l_{i+1} \leq k < i$ since $l_{i+1} = l_i$. Moreover, since $array[i] \geq p$, then $array[k] \geq p \, , \, l_{i+1} \leq k < i+1$, i.e statement 2) holds at step $i+1$

B. Else if $array[i] < p$. Then:

Before the swap: $array[i] < p$ (B.) and $array[l_i] \geq p$ as per statement 2) of $\mathcal{P} (i)$ with $k=l_i$.

So after the swap, $array[i] \geq p$ and $array[l_i] < p$

Also, the pointer l is moved to right: $l_{i+1} = l_i+1$.

Statement 1): $array[l_i] < p$ (after the swap), hence statement 1) is valid for $start \leq k \leq l_i$, which is equivalent to $start \leq k < l_{i+1}$ since $l_{i+1} = l_i+1$

Statement 2): which elements are greater than $p$ since the swap? Not $array[l_i]$ anymore. But elements at index $l_i + 1$, …, $i-1$ (if any) are still $\geq p$ as per statement 2) (step $i$). Moreover, $array[i]$ has now joined the club, since the swap. Then $array[k] \geq p \, , \, l_i + 1 \leq k < i + 1$, i.e. $array[k] \geq p \, , \, l_{i+1} \leq k < i + 1$

In both possible cases A. and B., $\mathcal{P} (i+1)$ holds.

Conclusion

We have proven:

$\mathcal{P} (0)$
$\mathcal{P} (0) \implies \mathcal{P} (1)$
$\mathcal{P} (1) \implies \mathcal{P} (2)$
…
$\mathcal{P} (end-1) \implies \mathcal{P} (end)$

From the above, we can conclude that $\mathcal{P} (end)$ holds:

$$ \mathcal{P} (end): \begin{cases} 1 ) \, array[k] < p \, , \, start \leq k < l_{end} \\[6pt] 2 ) \, array[k] \geq p \, , \, l_{end} \leq k < end \\ \end{cases} $$

The above is true at the beginning of step $i=end$, or more precisely at the end of step $i=end-1$ since the loop stops before $i=end$. At this point, one more instruction is executed: swapping $array[l_{end}]$ and $array[end]=p$. So, after the final swap, $array[l_{end}] = p$ and $array[end] \geq p$ (from $\mathcal{P} (end)$ - Statement 2). Finally:

$$ \begin{cases} array[k] < p \, , \, start \leq k < l_{end} \\[6pt] array[l_{end}] = p \\[6pt] array[k] \geq p \, , \, l_{end} \leq k \leq end \\ \end{cases} $$

Q.E.D.

Why the whole algorithm works

Now that the correctness of the partitioning part is established, we need to prove that recursively calling quick_sort(array) sorts array. This part is much easier than the correctness of the partition, and more documented as well.

When the size of the input array is 0 or 1, quick_sort() does nothing and the array is sorted
Suppose that quick_sort() adequately sorts any array of size $k \in \{ 0, 1, …, n \}, n \geq 1$
Then, let’s see what happens upon calling quick_sort() on an array of size $n+1$. First, the array will be partitioned in three parts: [left_part, pivot, right_part]. We have show in the previous section that pivot is already at the right index. Since all the elements of left_part are less than pivot, if the recursive call quick_sort(left_part) sorts the left part, then the job is done on the left side. Same logic for the right part. Well, the size of [left_part, pivot, right_part] is $s_l+1+s_r=n+1$, so $s_l+s_r \leq n$: left_part and left_part cannot be more than $n$ elements! So, by the inductive hypothesis, quick_sort(left_part) and quick_sort(left_part) do sort the arrays, and the array [left_part, pivot, right_part] of size $n+1$ ends up being sorted. The inductive statement holds at step $n+1$.

The above proves by strong induction that quick_sort sorts an array of any size $n \geq 0$.

References