Median-of-three pivot selection

Choose the median value among the first, middle and last entries of an active array segment. For at least three distinct sampled values, the selected value cannot be the whole segment's minimum or maximum. It can still be the second-smallest or second-largest value, so a balanced split does not follow. Coincident sample indices in segments of length one or two can be handled by the same comparison code. Ties must also have a defined branch policy.

A distinct-input counterexample for Quickselect that chooses the first/middle/last median, reserves it at the last slot, scans lower values to the front, and finally swaps the pivot into place. Let $A_n$ be the following permutation of $0,\dots ,n-1$. For $n<4$, take increasing order. For $n\ge 4$, let $B=A_{n-2}+2$ componentwise and $m=\lfloor n/2\rfloor$, then setand put $A_n(j)=B(j-2)$ at every other index $2\le j\le n-2$. These assignments use every entry of $B$ once and add zero and one, so they really define a permutation.

The sampled values are $1,0,B(m-2)$, with the last at least two, so the pivot is one. After the initial pivot swap, the only lower value is the zero at index $m$. Moving it to the front places the displaced $B(m-2)$ at its intended tail position. The final pivot swap moves $B(n-3)$ from index one to the last position. Every other tail entry already has its intended position. Thus the complete partitioned result is exactly $[0,1]$ followed by $B$.

Selecting the maximum consequently repeats the same construction on $n-2$ entries. If $C(n)$ counts only pivot comparisons made by the partition scan, then $C(n)=n-1+C(n-2)$, with $C(1)=0$ and $C(2)=1$. Hence $C(n)=\lfloor n^2/4\rfloor$ and total runtime is $\Theta (n^2)$. For example, $A_6=[1,4,3,0,2,5]$. This disproves a linear worst-case claim even when every value is distinct.