Hoare partition scheme may cause infinite recursion

Question

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]

Answer 1

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.