Hoare Partition Quicksort

Hoare partition quicksort uses the original two pointer partition scheme introduced by Tony Hoare. It scans from both ends of the range, swaps misplaced elements, and returns a split point.

Compared with Lomuto partition, Hoare partition usually performs fewer swaps and handles many inputs more efficiently. Its return value is a boundary, not necessarily the final position of the pivot.

Problem

Given an array $A$ of length $n$ , reorder it such that:

A[0] \le A[1] \le \dots \le A[n-1]

Idea

Choose a pivot value. Move one pointer from the left until it finds an element at least as large as the pivot. Move another pointer from the right until it finds an element at most as small as the pivot. If the pointers have not crossed, swap those two elements.

After the pointers cross, every element on the left side is less than or equal to every element on the right side with respect to the pivot boundary.

Algorithm

hoare_quicksort(A, lo, hi):
    if lo >= hi:
        return

    p = hoare_partition(A, lo, hi)

    hoare_quicksort(A, lo, p)
    hoare_quicksort(A, p + 1, hi)

hoare_partition(A, lo, hi):
    pivot = A[(lo + hi) // 2]
    i = lo - 1
    j = hi + 1

    while true:
        repeat:
            i += 1
        until A[i] >= pivot

        repeat:
            j -= 1
        until A[j] <= pivot

        if i >= j:
            return j

        swap A[i] and A[j]

Example

Let:

A = [4, 7, 2, 1, 5, 3]

Choose middle pivot:

p = 2

Partitioning moves values less than or equal to $2$ leftward and values greater than or equal to $2$ rightward. One possible partition result is:

[1, 2, 7, 4, 5, 3]

The returned boundary separates the two recursive ranges.

Correctness

The partition loop maintains two scanning regions. Elements before the left pointer have already been checked against the pivot, and elements after the right pointer have already been checked against the pivot. When two misplaced elements are found, swapping them restores the partition condition for those positions.

When the pointers cross, no misplaced pair remains. The returned index separates the range into two smaller ranges. Recursively sorting both ranges produces a sorted array.

Complexity

case	time
best	$O(n \log n)$
average	$O(n \log n)$
worst	$O(n^2)$

Space:

case	space
average recursion	$O(\log n)$
worst recursion	$O(n)$

Properties

property	value
stable	no
in-place	yes
swaps	fewer than Lomuto on many inputs
pivot final position	not guaranteed
implementation difficulty	moderate

Notes

Hoare partition is efficient but easy to implement incorrectly. The recursive calls must use:

[lo, p]

and

[p + 1, hi]

rather than excluding $p$ as if it were the final pivot position.

This distinction is the main source of bugs.

Implementation

def hoare_quicksort(a):
    def sort(lo, hi):
        if lo >= hi:
            return

        p = partition(lo, hi)
        sort(lo, p)
        sort(p + 1, hi)

    def partition(lo, hi):
        pivot = a[(lo + hi) // 2]
        i = lo - 1
        j = hi + 1

        while True:
            i += 1
            while a[i] < pivot:
                i += 1

            j -= 1
            while a[j] > pivot:
                j -= 1

            if i >= j:
                return j

            a[i], a[j] = a[j], a[i]

    sort(0, len(a) - 1)
    return a

func HoareQuickSort(a []int) {
	var sort func(int, int)

	sort = func(lo, hi int) {
		if lo >= hi {
			return
		}

		p := hoarePartition(a, lo, hi)
		sort(lo, p)
		sort(p+1, hi)
	}

	sort(0, len(a)-1)
}

func hoarePartition(a []int, lo, hi int) int {
	pivot := a[(lo+hi)/2]
	i := lo - 1
	j := hi + 1

	for {
		for {
			i++
			if a[i] >= pivot {
				break
			}
		}

		for {
			j--
			if a[j] <= pivot {
				break
			}
		}

		if i >= j {
			return j
		}

		a[i], a[j] = a[j], a[i]
	}
}