= Solution
Test singleton and two-element segments, first/last/interior requested ranks, nonzero segment offsets, already sorted and reversed inputs, random inputs, all-equal inputs and several patterns of duplicates. Include `Int.MinValue` and `Int.MaxValue` to expose overflow-prone comparisons. An independent sorted copy supplies the value oracle; also check preservation of the segment's <multiset> and of all outside entries. For speed tests, increase segment size and include deliberately unfavorable pivot arrangements, rather than timing random inputs alone.
\b[Distinct entries do not guarantee linear worst-case time: the worst case is $\Theta(N^2)$.] A median of three can repeatedly be the second-smallest remaining value, leaving a segment of size $N-2$ when seeking its maximum. The <quadratic median-of-three selection family> gives explicit distinct inputs realizing this behavior for the implementation above; one six-entry member is $[1,4,3,0,2,5]$. Its recurrence is $T(N)=T(N-2)+\Theta(N)$, yielding a quadratic sum. Balanced reductions instead give $T(N)=T(N/2)+\Theta(N)=\Theta(N)$. Randomized or suitable average-case analyses give expected linear selection, but this deterministic heuristic alone supplies no such worst-case guarantee. Unlike <Quicksort>, <Quickselect> explores only one side, so a balanced run is linear rather than $\Theta(N\log N)$.
Back to article page
