# Quicksort with Hoare's Partition Algorithm

I've came across Hoare's partition algorithm in Cormen. After analysis I think that the algorithm isn't working as I expected. Let's suppose that we've array [4,3,2,1], then in my opinion partition is returning 0, so next quicksort calls will be QS(A,1,0), QS(A,1,4), the second one is the same as first call so this array won't be sorted ever (infinite recursion).

Partition(A,p,r)
x = A[p]
i = p-1
j = r+1
while True do
repeat j-=1
until x>=A[j]
repeat i+=1
until x<=A[i]
if i<j then
swap(A[i], A[j])
else
return j

QS(A,p,r)
q = Partition(A,p,r)
QS(A,p,q)
QS(A,q+1,r)

• Please double check your reasoning, especially the indices. Have you implemented the pseudocode in your favorite programming language? What is the result if you run it? Have you done the exercise "Hoare partition correctness" in the book? QS(A,1,0)? – Apass.Jack Apr 10 at 19:15
• Once upon a time I have analyzed variations of this algo: cs.stackexchange.com/questions/92562/… – Bulat Apr 10 at 21:04