Hoare partition scheme may cause infinite recursion

Wiki states: "...partitioning algorithm guarantees lo ≤ p < hi which implies both resulting partitions are non-empty, hence there's no risk of infinite recursion."

What prevents Hoare partition from not returning j equal to hi? If our pivot is max number, we may execute j <- j – 1 only once and exit with j=hi

E.g. A= [2,0]


Some implementations add a final swap of placing the initially chosen pivot into returned j:

swap A[lo] with A[j]
return j


What would guarantee p < hi?

Full pseudo-code from wiki:

algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
do
i := i + 1
while A[i] < pivot

do
j := j - 1 <------------- execute once
while A[j] > pivot

if i >= j then
return j <------------- exit

swap A[i] with A[j]


Did you notice the outer loop, loop forever?

Let us say in the first iteration of that loop forever loop, we have just finished the second inner loop, do j := j - 1 while A[j] > pivot.

• If j := j-1 has been executed at least twice, then j <= (hi+1)-2 = hi-1.

• Otherwise j := j-1 has been executed exactly once. Then
$$\quad\quad$$j = (hi+1)-1 = hi.
Note that the first inner loop, do i := i + 1 while A[i] < pivot produces
$$\quad\quad$$ i = lo
since i = lo - 1 initially and A[lo] = pivot.

Now we execute if i >= j then return j. Since the condition i >= j does not hold as lo < hi (the pseudocode for quicksort specifies that only when lo < hi shall partition be performed), the code return j will be skipped, i.e., we shall go on with the next iteration of that loop forever loop. In that next iteration, j := j-1 will be executed again, causing j < hi.

So, we will always have j < hi at some point of time during the partition. Since j would never increase, we will have j < hi when we return j. $$\quad\checkmark$$

The analysis above holds regardless of whether our pivot is the max number or not.

• On the 1st iteration of the outer loop <i> always stays equal to <lo>. That means the outer loop will be executed 2 or more times. Never once. Thank you, John L. It closes my gap with different variations (old Cormen) where it starts rolling <j> prior to <i>
– belz
Jul 5 '21 at 13:25