# Quicksort Median of Three

# 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

```text id="g8k2ps"
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)
```

```text id="m2v9xe"
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

```python id="v4q7mk"
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
```

```go id="c8k4xs"
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
}
```