Lomuto partition

A simple way to partition for quicksort: use the last element as the pivot and sweep left to right, swapping smaller items to the front.

In more detail

A boundary index tracks where the "smaller than pivot" region ends; when the sweep finds a smaller item it swaps it to the boundary and advances it. At the end the pivot is swapped into the boundary, its final place. It is easy to get right but performs badly on inputs with many equal keys.

Related terms

Taught in

References