How does Hoare's quicksort work, even if the final position of the pivot after partition() is not what its position is in the sorted array?
I've been looking into examples and sorting arrays myself via Hoare's quicksort. I think I've found another interesting pattern in Hoare's partition algo. Which may explain why Hoare's method works. Lomuto divides the array into three parts; elements smaller than the pivot, the pivot, elements greater than the pivot. I think Hoare looks at things differently. He divides the array into two parts; elements smaller than the pivot, elements equal to or greater than the pivot. One of the traps that I fell into was that Lomuto's partition returns the final position of the pivot, whereas Hoare's partition returns the position just before the final position of the pivot. This is why Lomuto then quick sorts from lo to p-1, whereas Hoare quick sorts from lo to p. Another inference that can be drawn is that if Hoare's partition returned i instead of j, we'd then divide the array into two parts- from lo to i-1 and from i+1 to hi, just like Lomuto did. And it only took me 4 hours to understand that.