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

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)

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

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

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
}