Quickselect

A selection algorithm that uses array partitioning around a pivot and recursively searches only the side containing the desired order statistic. If there are $s$ entries before the placed pivot, an earlier rank is unchanged and a later rank is reduced by $s+1$. Segment length strictly decreases, proving algorithm termination. The same reduction can update local bounds in a loop, using constant auxiliary space.

Balanced reductions give linear work by a geometric series, while repeatedly discarding only a constant number of entries can give quadratic work. For distinct entries and independent uniform random pivots, a pivot in the middle half has probability at least one half and reduces the retained length to at most three quarters, up to rounding. The expected number of attempts for each such reduction is bounded, so summing expected work over geometric size scales gives $O(n)$ expected time. This random-pivot guarantee is not a worst-case guarantee for a deterministic median-of-three heuristic. With duplicates and a strict two-way partition, random pivot choice alone can also fail to shrink an all-equal segment; a three-way partition treats equal keys together.

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.