Partition

Partition arranges the subarray so that elements <= Pivot are on the left and elements >= Pivot are on the right (variations differ in details). The Pivot ends up in its final position.

Lomuto and Hoare are common schemes.

Where used

Core of Quicksort and Selection (Quickselect). The same idea is behind Dutch-National-Flag partitions and in-place reorderings.

Depth

A partition rearranges a region so that values on different sides fulfill a relation to the pivot. Lomuto typically uses a boundary for the smaller region and a scan index. Hoare moves two pointers from the outside in and swaps incorrectly placed pairs.

The return value has a different meaning depending on the scheme. In Lomuto, it is often a pivot position, while in Hoare, it is usually a separator for two additional intervals. Correct recursion boundaries must therefore follow from the used scheme and must not be mixed between variants.

Difficulty levels

1. Track the area invariants of a partition scheme.
2. Appropriately combine return value and recursive intervals.
3. Analyze behavior with many values equal to the pivot.

Pitfalls

Many Quicksort errors arise not in comparisons but due to inconsistent interval conventions. Inclusive and exclusive bounds must not change unnoticed within an implementation.