Hoare partition scheme

The Hoare partition scheme is the original partitioning method developed by Tony Hoare for Quicksort in 1959. It operates by selecting a pivot and using two indices that converge from opposite ends of the subarray, swapping elements that are on the wrong side of the pivot until the indices cross. This bidirectional approach performs fewer swaps than simpler alternatives and exhibits superior cache locality because it scans contiguous memory regions from both directions rather than making fragmented jumps.

Hoare's scheme is subtly more complex to implement correctly than the Lomuto alternative, but its efficiency is not merely a constant-factor optimization. It is a structural choice: by minimizing the number of memory writes, Hoare partitioning reduces the algorithm's bandwidth footprint, which becomes the binding constraint as array sizes exceed cache capacity. The scheme's elegance lies in its symmetry — the pivot does not necessarily end in its final position, but both resulting partitions are guaranteed sortable by recursive application.