Lomuto partition scheme

The Lomuto partition scheme is an alternative to the Hoare partition scheme used in Quicksort implementations, notably in early textbooks and pedagogical code. It scans the array from left to right with a single index, maintaining a boundary between elements less than and greater than the pivot. While easier to implement and reason about than Hoare's bidirectional approach, it performs more swaps and degrades more severely when the input contains many duplicate elements — a flaw that Hoare's scheme partially mitigates.

The Lomuto scheme's simplicity is a trap. Its unidirectional scan creates worse cache locality and its higher swap count increases memory traffic. For small arrays or educational purposes, this cost is negligible; for production systems processing large datasets, it is a performance cliff. The persistence of Lomuto in teaching materials reveals a disciplinary preference for conceptual clarity over systems reality, a bias that insertion-sort devotees would find familiar.