Implementation: Hoare/Lomuto-light Partition

Implement a simple Lomuto partition using the last element as the pivot.

Anyone writing a partition understands Quicksort bugs and off-by-one errors at the boundaries. It is useful when reading JDK and teaching code.

Depth

A Lomuto-light variant can choose the last element as the pivot. Before the scan, only values that correspond to the chosen relation are on the left of the boundary; between the boundary and the scan, already examined values of the other group lie. After the scan, the pivot is set at the boundary.

A Hoare-close variant uses two indices and swaps pairs that are on the wrong side. It often requires fewer swaps, but its return value defines a boundary. Both variants are correct when invariants, comparison operators, and recursive intervals match.

Difficulty levels

1. Check a Lomuto invariant during each scan step.
2. Ensure safe progress for Hoare pointers with duplicates.
3. Specify correct recursive sub-intervals for each schema.

Pitfalls

Mixed rules are dangerous, such as a Hoare return value with Lomuto boundaries. When there are the same pivot values, pointers must still make progress to ensure the loop terminates.