Quicksort Median of Three

Quicksort median of three improves pivot selection by choosing the median value among the first, middle, and last elements of the current range. This avoids some common bad cases, such as already sorted or reverse sorted arrays, where choosing the first or last element as pivot can produce highly unbalanced partitions.

The algorithm keeps the same recursive structure as quicksort. Only the pivot selection step changes.

Problem

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

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

Idea

For a range $A[lo..hi]$, inspect three candidates:

$$ A[lo],\quad A[mid],\quad A[hi] $$

where

$$ mid = \lfloor (lo + hi) / 2 \rfloor $$

Choose the median of these three values as the pivot.

This is a small sampling strategy. It often gives a better pivot than blindly choosing one endpoint.

Algorithm

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

    pivot_index = median_of_three(A, lo, hi)
    swap A[pivot_index] and A[hi]

    p = partition(A, lo, hi)

    median_of_three_quicksort(A, lo, p - 1)
    median_of_three_quicksort(A, p + 1, hi)

median_of_three(A, lo, hi):
    mid = (lo + hi) // 2

    if A[lo] > A[mid]:
        swap A[lo], A[mid]
    if A[mid] > A[hi]:
        swap A[mid], A[hi]
    if A[lo] > A[mid]:
        swap A[lo], A[mid]

    return mid

Example

Let:

$$ A = [9, 2, 7, 4, 1] $$

For the whole range:

position	value
first	9
middle	7
last	1

Sorted candidates:

$$ 1,\ 7,\ 9 $$

Median pivot:

$$ 7 $$

Partition around $7$:

$$ [2, 4, 1, 7, 9] $$

Then recursively sort the two sides.

Correctness

Median of three changes only the pivot selection rule. Partitioning still places the chosen pivot in its final sorted position, with no larger elements on the left and no smaller elements on the right. The recursive calls sort both sides, so the whole range becomes sorted.

Complexity

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

Median of three improves the likelihood of balanced partitions, but it does not remove the quadratic worst case.

Space:

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

Properties

property	value
stable	no
in-place	yes
randomized	no
pivot quality	better than endpoint pivot
implementation cost	low

Notes

Median of three is a practical default for quicksort implementations. It is especially useful against already sorted input, reverse sorted input, and simple patterned data.

For stronger protection, combine it with introsort, three way partitioning, or randomized fallback.

Implementation

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

        pivot_index = median_of_three(lo, hi)
        a[pivot_index], a[hi] = a[hi], a[pivot_index]

        p = partition(lo, hi)

        sort(lo, p - 1)
        sort(p + 1, hi)

    def median_of_three(lo, hi):
        mid = (lo + hi) // 2

        if a[lo] > a[mid]:
            a[lo], a[mid] = a[mid], a[lo]
        if a[mid] > a[hi]:
            a[mid], a[hi] = a[hi], a[mid]
        if a[lo] > a[mid]:
            a[lo], a[mid] = a[mid], a[lo]

        return mid

    def partition(lo, hi):
        pivot = a[hi]
        i = lo

        for j in range(lo, hi):
            if a[j] <= pivot:
                a[i], a[j] = a[j], a[i]
                i += 1

        a[i], a[hi] = a[hi], a[i]
        return i

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

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

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

		pivotIndex := medianOfThree(a, lo, hi)
		a[pivotIndex], a[hi] = a[hi], a[pivotIndex]

		p := partitionMedianThree(a, lo, hi)

		sort(lo, p-1)
		sort(p+1, hi)
	}

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

func medianOfThree(a []int, lo, hi int) int {
	mid := (lo + hi) / 2

	if a[lo] > a[mid] {
		a[lo], a[mid] = a[mid], a[lo]
	}
	if a[mid] > a[hi] {
		a[mid], a[hi] = a[hi], a[mid]
	}
	if a[lo] > a[mid] {
		a[lo], a[mid] = a[mid], a[lo]
	}

	return mid
}

func partitionMedianThree(a []int, lo, hi int) int {
	pivot := a[hi]
	i := lo

	for j := lo; j < hi; j++ {
		if a[j] <= pivot {
			a[i], a[j] = a[j], a[i]
			i++
		}
	}

	a[i], a[hi] = a[hi], a[i]
	return i
}