Start by recalling the core idea behind Hoare's partition scheme: it divides the array into two parts where elements in the left part are less than or equal to the pivot, and elements in the right part are greater than or equal to the pivot.

Consider the boundary conditions: What happens when the pivot is the smallest or largest element in the array? How does the algorithm handle duplicate elements?

Prove correctness by analyzing the loop invariants: Show that after each iteration of the partitioning loop, the following holds: