# 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)? Apr 10, 2019 at 19:15
• Once upon a time I have analyzed variations of this algo: cs.stackexchange.com/questions/92562/… Apr 10, 2019 at 21:04
• I also had some trouble implementing this. I was integrating this into a dynamic language where you can easily test the @#\$% out of something. In one line I can generate all permiutations of a sequence, sort them, and uniq them to test that they are all identical to each other, and compare to the tested result. I simply iterated on tweaking the details until that test case passed: all possible permutations of 1..9 were being sorted to 1..9. Then added larger test cases.
– Kaz
May 2, 2023 at 5:42