# Quicksort Ninther

# Quicksort Ninther

Quicksort ninther improves pivot selection by using a stronger sampling strategy called Tukey's ninther. Instead of taking the median of three elements, it takes the median of three medians, each computed from three elements.

This increases the likelihood of selecting a pivot close to the true median, which leads to more balanced partitions.

## Problem

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

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

## Idea

Select nine elements from the range and group them into three triples:

$$
(a_1,a_2,a_3),\quad (a_4,a_5,a_6),\quad (a_7,a_8,a_9)
$$

Compute the median of each triple:

$$
m_1,\quad m_2,\quad m_3
$$

Then choose the pivot as:

$$
\text{median}(m_1, m_2, m_3)
$$

This is called the ninther.

## Algorithm

```text id="p6r2xd"
ninther_quicksort(A, lo, hi):
    if lo >= hi:
        return

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

    p = partition(A, lo, hi)

    ninther_quicksort(A, lo, p - 1)
    ninther_quicksort(A, p + 1, hi)
```

```text id="k3s9qt"
ninther(A, lo, hi):
    step = (hi - lo) // 8

    i1 = lo
    i2 = lo + step
    i3 = lo + 2 * step

    i4 = lo + 3 * step
    i5 = lo + 4 * step
    i6 = lo + 5 * step

    i7 = lo + 6 * step
    i8 = lo + 7 * step
    i9 = hi

    m1 = median_of_three(A, i1, i2, i3)
    m2 = median_of_three(A, i4, i5, i6)
    m3 = median_of_three(A, i7, i8, i9)

    return median_of_three(A, m1, m2, m3)
```

## Example

Let:

$$
A = [9,1,8,2,7,3,6,4,5]
$$

Divide into triples:

* [9,1,8] → median 8
* [2,7,3] → median 3
* [6,4,5] → median 5

Final pivot:

$$
\text{median}(8,3,5) = 5
$$

Partition around $5$:

$$
[1,2,3,4,5,6,7,8,9]
$$

## Correctness

The ninther method changes only pivot selection. Partitioning and recursion follow standard quicksort rules, so correctness remains unchanged.

## Complexity

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

The probability of highly unbalanced partitions is significantly reduced compared to simple pivot selection.

Space:

| case    | space       |
| ------- | ----------- |
| average | $O(\log n)$ |
| worst   | $O(n)$      |

## Properties

| property      | value                       |
| ------------- | --------------------------- |
| stable        | no                          |
| in-place      | yes                         |
| pivot quality | high                        |
| overhead      | higher than median of three |

## Notes

Ninther improves partition balance and reduces recursion depth variance. It is particularly useful for large arrays where pivot quality strongly affects performance.

However, it introduces extra comparisons during pivot selection, so it is usually used only for sufficiently large subarrays.

## Implementation

```python id="v3p9kx"
def ninther_quicksort(a):
    def sort(lo, hi):
        if lo >= hi:
            return

        pivot_index = ninther(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(i, j, k):
        vals = [(a[i], i), (a[j], j), (a[k], k)]
        vals.sort()
        return vals[1][1]

    def ninther(lo, hi):
        step = max((hi - lo) // 8, 1)

        i1 = lo
        i2 = lo + step
        i3 = lo + 2 * step

        i4 = lo + 3 * step
        i5 = lo + 4 * step
        i6 = lo + 5 * step

        i7 = lo + 6 * step
        i8 = lo + 7 * step
        i9 = hi

        m1 = median_of_three(i1, i2, i3)
        m2 = median_of_three(i4, i5, i6)
        m3 = median_of_three(i7, i8, i9)

        return median_of_three(m1, m2, m3)

    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="z8k2qf"
func NintherQuickSort(a []int) {
	var sort func(int, int)

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

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

		p := partitionNinther(a, lo, hi)

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

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

func medianOfThreeIdx(a []int, i, j, k int) int {
	if a[i] > a[j] {
		i, j = j, i
	}
	if a[j] > a[k] {
		j, k = k, j
	}
	if a[i] > a[j] {
		i, j = j, i
	}
	return j
}

func ninther(a []int, lo, hi int) int {
	step := (hi - lo) / 8
	if step == 0 {
		step = 1
	}

	i1 := lo
	i2 := lo + step
	i3 := lo + 2*step

	i4 := lo + 3*step
	i5 := lo + 4*step
	i6 := lo + 5*step

	i7 := lo + 6*step
	i8 := lo + 7*step
	i9 := hi

	m1 := medianOfThreeIdx(a, i1, i2, i3)
	m2 := medianOfThreeIdx(a, i4, i5, i6)
	m3 := medianOfThreeIdx(a, i7, i8, i9)

	return medianOfThreeIdx(a, m1, m2, m3)
}

func partitionNinther(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
}
```