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 since lo < hi (only when lo < hi shall we perform partition), so the code return j will be skipped, i.e., we will 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 < h when we return j. $\quad\checkmark$

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

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.