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. Tighter and faster than the simpler Lomuto partition taught in most textbooks, but the invariants are subtler and the recursive setup more delicate.

Hoare averages about $1/3$ as many swaps as Lomuto and handles duplicate-heavy inputs better. The catch: 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);
    }
}

Common mistake: writing quicksort_hoare(arr, lo, p-1) and quicksort_hoare(arr, p+1, hi) like in Lomuto. That’s 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 is one of two standard partitioning schemes for Quick sort; the simpler alternative is Lomuto partition. Production sort libraries combine partitioning with insertion-sort for small arrays and switch to Heap sort on adversarial input — see introsort.

Idriss Rami — Notes

Explorer