In Algorithms, 4th Edition, I read that after the partitioning step one element is in its final position.
The entry a[j] is in its final place in the array, for some j.
No entry in a[lo] through a[j-1] is greater than a[j].
No entry in a[j+1] through a[hi] is less than a[j].
And this comes from Algorithms, 4th Edition, as well:
First, we arbitrarily choose a[lo] to be the partitioning item—the one that will go into its final position.
Does the pivot go into its final position for all inputs without exception?