Quick sort, Hoare's partition algorithm. Is there a mistake in CLRS? The following problem appears in &quot;Introduction to Algorithms&quot; by Thomas Cormen et. al., aka CLRS.
Problem 7-1.b
Hoare's partition algorithm from the book.

Part b: Assuming the subarray $A[p,\cdots,r]$ contains at least two elements, show that the indices $i$ and $j$ are such that we never access an element of outside the subarray $A[p,\cdots,r]$

I think this it is not possible to prove this because this statement is not correct, i.e., during the course of execution we happen to access elements outside the array.
Here I prove the converse of part b by using a counter-example.
Consider the array A = [1,2]. Let p = 1 and there r =2.

Initially, $i = 0$, $j = 3$ and $x = 1$.
After the loop $5-7$ executes once, $j$ becomes 2 and the condition in line 7 fails resulting the termination of the loop $5-7$.
Now we reach the loop $8-10$. Now let's look at the state after this loop executes twice. $i = 2$ and the condition in line 10 still holds. Therefore the loop executes a third time and $i$ becomes 3.
Now to test the condition in line 10 we access $A[3]$ which is outside the subarray $A[1,\cdots, 2]$


Is there a mistake in my reasoning or is the problem statement wrong?
The problem statement is correct.
I think you getting confused about: repeat $j \gets j-1$ until $A[j] \leq x$. It means that if $A[j]&gt;x$ then do $j \gets j-1$.
Similarly, loop $8-10$ means that if $A[i]&lt;x$ then do $i \gets i+1$.
Therefore, the algorithm executes in the following way on $A = [1,2]$:

After the loop $5-7$, $j$ becomes $1$ since $A[2] &gt; x$.

After loop $8−10$, $i$ becomes $1$ since $A[1] = x$.

Since $i = j = 1$, the algorithm terminates and returns $1$.