I am having trouble seeing why in the inner while-loops, the condition $i\le j$ is needed in addition to checking $M[i]\le p$ (or $M[i]\gt p$). The pseudocode given in the Wikipedia article does not seem to do this additional check. There is a potential problem in the given implementation that if all elements in $M[l+1..r]$ are less than $p$, the first while loop would not terminate when not checking for $i≤j$. However, that does not explain the necessity of checking $i≤j$ in the second inner while loop.
As you suspected, it is not needed to check the condition $i≤j$ in the second inner while loop.
One usual way to prove that condition is not needed is by analyzing all possible cases and establishing various invariants as well as employing the powerful tool of mathematical induction, which will probably convince anyone who can follow through the proof with enough patience. Although I have done that below, it is actually not convincing to myself because of the subtlety in the
Hoare's quicksort as shown in Hoare's quicksort is deceptively simple, the devil in selecting element at index hi as pivot, a slight modification of Hoare's partitioning, what happens if both indexes land on the pivot. Even if I have checked my proof tens of times, it might still miss a corner case or two. As shown/implied by many answers at why is writing down mathematical proofs more fault-tolerant than writing computer code?, a traditional mathematical proof for a moderate computer program is probably far from fully satisfactory or fully correct in general. It is more like how we can understand/believe the program is correct in a high level.
Instead, I have written a program that tests the implementation of Hoare's quicksort with that condition removed.
That program tests the sorting algorithm against every permutation of every possible way $n$ competitors can rank in a competition, allowing for the possibility of ties, up to a certain number of competitors.
What are all possible ways $n$ competitors can rank in a competition? Here is an example for $n=3$. There are four different sorted ranks, [1, 1, 1], [1, 2, 2], [1, 1, 2] and [1, 2, 3]. If a comparison sorting algorithm can sort all permutations of each of those four arrays, which counts to 13, it will sort any array of size 3 correctly. By the way, the number of ways $n$ competitors can rank in a competition is the Fubini numbers.
If a simple sorting algorithm like the current one does not work, it should fail for an array whose size is smaller than 8. For extra insurance, I have run that program against arrays size up to 11. These testing proves that condition is not needed.
A brief mathematical proof
Since many people would prefer a traditional proof, here is a sketch of a mathematical proof of the correctness of the implementation either with or without that additional check.
Let us assume l < r. Throughout the method, M is a constant reference to the array while l and r are constant indices. The pivot p = M[l] is constant, too. All we need to prove is that at the end of outer while loop, M[l] is the pivot, followed by elements not bigger than the pivot up to index j inclusively or no elements if l >= j, followed by all other elements, which are bigger than the pivot. (Then by mathematical induction on r - l, we can prove easily that the method does sort the subarray of M from indice r to l inclusively.)
- We can establish the following invariant at the end of each iteration of the outer while loop.
- Elements from
l + 1 to the smaller of i and j are not bigger than the pivot
- Elements from
j + 1 to r are bigger than the pivot.
- The first inner loop,
while ( i <= j && M[i] <= p) { i = i + 1; } will find the smallest index i such that i <= j && M[i] > p or i == j+1.
The second inner loop, either while (M[j] > p) { j = j - 1; } or while (i <= j && M[j] > p) { j = j - 1; } will find the largest $j$ such that M[j] <= p.
Why is the condition i <= j not necessary? Let us elaborate as here is the crux of current question.
There are two cases at the start of this loop depending on the result of above inner loop.
i <= j && M[i] > p. As we are looking for an element that is not larger than the pivot going from index j to smaller indices, the latest time we will succeed must before current i. That is, i <= j will always be satisfied throughout the loop. That is, the condition i <= j is not necessary.i == j+1. The first inner loop must have missed the above case, since j is smaller than j + 1. That means M[j] > p was not satisfied. So at the start of current loop, we have both i > j and M[j] <= p. Using either version of the second inner while loop, we will break the loop right away.
if (i < j) { swap(M, i, j);}. This swap extends both the left hand side of elements that is not bigger than the pivot and the right hand side of elements that is bigger than the pivot.
To tell the truth, I used program to double check various invariants and propositions in the mathematical proof.
Many further questions can be raised, which go much beyond the scope of the current question.
- How to improve the performance of the testing problem?
- How to reduce the number of test cases needed for a specific size?
- Is there a way to determine rigorously an upper bound of the size of the array that need to be tested to prove the correctness of a sorting algorithm given its description?
