 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.

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)$.