Hoare partition

The Hoare partition scheme is the partitioning method Tony Hoare published with his original quicksort paper in 1961. Two pointers walk inward from opposite ends of the array, swapping pairs of elements that are on the wrong side of the pivot. The result is a tighter, faster partition than the simpler Lomuto partition taught in most textbooks — but with subtler invariants and a more delicate recursive setup.

The win: Hoare averages about $1/3$ as many swaps as Lomuto and handles duplicate-heavy inputs more gracefully. The cost: the returned index is not the pivot’s final position, so the recursion has to be set up differently.

Algorithm

int hoare_partition(int arr[], int lo, int hi) {
    int pivot = arr[lo + (hi - lo) / 2];   // middle element
    int i = lo - 1;
    int j = hi + 1;
    while (1) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;              // split point
        swap(&arr[i], &arr[j]);
    }
}

The two do-while loops advance i rightward (skipping elements already on the correct side, those < pivot) and j leftward (skipping elements > pivot). When both stop, arr[i] >= pivot and arr[j] <= pivot — the two are out of place, so swap them.

When i and j cross (i >= j), the split is complete.

The invariant when each outer iteration starts:

arr[lo..i-1] ≤ pivot.
arr[j+1..hi] ≥ pivot.

When i and j cross, every element to the left of the split is ≤ pivot and every element to the right is ≥ pivot. The two halves overlap in pivot-equal elements but never share an index, so the recursion still shrinks.

Worked example

Array [3, 8, 2, 5, 1, 4, 7, 6], pivot = arr[(0+7)/2] = arr[3] = 5. The do-while semantics matter — i always advances at least once per outer iteration, and so does j. Step through carefully:

Init i = -1, j = 8, pivot = 5.

Outer iteration 1:

do i++ while arr[i] < pivot: i=0, arr[0]=3<5 → i=1, arr[1]=8≮5 → stop. i=1.
do j-- while arr[j] > pivot: j=7, arr[7]=6>5 → j=6, arr[6]=7>5 → j=5, arr[5]=4≯5 → stop. j=5.
i=1 < j=5, swap arr[1] ↔ arr[5]: [3, 4, 2, 5, 1, 8, 7, 6].

Outer iteration 2:

do i++ while arr[i] < pivot: i=2, arr[2]=2<5 → i=3, arr[3]=5≮5 → stop. i=3.
do j-- while arr[j] > pivot: j=4, arr[4]=1≯5 → stop. j=4.
i=3 < j=4, swap arr[3] ↔ arr[4]: [3, 4, 2, 1, 5, 8, 7, 6].

Outer iteration 3:

do i++ while arr[i] < pivot: i=4, arr[4]=5≮5 → stop. i=4.
do j-- while arr[j] > pivot: j=3, arr[3]=1≯5 → stop. j=3.
i=4 ≥ j=3, return j=3.

Final array: [3, 4, 2, 1, 5, 8, 7, 6]. Split at index 3.

Left half arr[0..3] = [3, 4, 2, 1] — all ≤ 5. Right half arr[4..7] = [5, 8, 7, 6] — all ≥ 5. Correct.

Note that the returned j = 3 is not the pivot’s final position — 5 ended up at index 4, and j returned 3.

Quicksort with Hoare

void quicksort_hoare(int arr[], int lo, int hi) {
    if (lo < hi) {
        int p = hoare_partition(arr, lo, hi);
        quicksort_hoare(arr, lo, p);       // note: includes p
        quicksort_hoare(arr, p + 1, hi);
    }
}

The conventional pitfall: writing quicksort_hoare(arr, lo, p-1) and quicksort_hoare(arr, p+1, hi) like in Lomuto. That is wrong for Hoare — p is not the pivot’s final position, just a split index, and excluding it can drop elements from both halves. The left recursion must include p.

Why fewer swaps than Lomuto

Lomuto swaps every time it finds an element ≤ pivot — typically about $n /2$ swaps per partition (half the array is ≤ pivot, on average). Hoare only swaps when both pointers find elements on the wrong side, which is rarer because most elements are already on the correct side and just get scanned past.

Empirically Hoare averages about $n /6$ swaps per partition, vs. $n /2$ for Lomuto. Each swap is three writes; cutting them by 3× is a real practical win on cache-bound workloads.

Pivot choice

The example used the middle element. The choice matters:

First or last — bad for already-sorted input (worst-case $O (n^{2})$ ).
Middle — works well for sorted input, can still go bad on adversarial.
Random — adversarial inputs become unlikely.
Median of three (first, middle, last) — combines the benefits, costs a few extra comparisons.

Production-grade quicksort variants (introsort, dual-pivot) typically use median-of-three or a 5-element ninther.

When swap counts matter — duplicate-heavy inputs

If many elements equal the pivot, Hoare’s pointers will both stop on those equal elements (because the do-while conditions are strict $<$ and $>$ , not $\leq$ and $\geq$ ). The pointers then cross somewhere in the middle of the duplicates, so duplicates spread evenly across both halves rather than piling on one side as Lomuto would. This makes Hoare $O (n lo g n)$ even with many duplicates, while Lomuto degrades.

Pitfalls

The off-by-one in the recursive call. Already mentioned: (lo, p) and (p+1, hi), not (lo, p-1).
Strict inequalities matter. Using ≤ and ≥ instead of < and > in the inner loops causes the pointers to advance past equal elements, which can leave the partition unbalanced or cause infinite recursion in pathological cases.
Pivot from end positions. With pivot = arr[hi] (and i = lo, j = hi-1 start), Hoare can break in subtle ways with sorted input — the middle-element pivot dodges this.

Hoare vs Lomuto — quick comparison

Aspect	Lomuto	Hoare
Pointers	One boundary, one scanning	Two inward-walking
Pivot position after	Final	Not at returned index
Swaps per partition	~n/2	~n/6
Recursion form	`(lo, p-1), (p+1, hi)`	`(lo, p), (p+1, hi)`
Handles duplicates	Poorly (cluster on one side)	Well (split between sides)
Clarity	Easier	Harder
Used in	Teaching, simple implementations	Production sort libraries

In context

Hoare partition is one of two standard partitioning schemes for Quick sort. The simpler alternative is Lomuto partition. For modern production sort libraries that combine the partitioning ideas with insertion-sort for small arrays and switching to Heap sort on adversarial input, look up introsort.

Idriss Rami — Notes

Explorer