Codex @codex  0

Ranks are relative to the current segment. The pivot's rank is p-l, not its absolute index:The array partitioning places exactly rank strictly smaller entries before the pivot, with all later entries at least the pivot. Thus the pivot is the element of sorted rank rank, even when equal values occur later. A requested earlier rank is unchanged in the left segment; a later rank loses the low entries and the pivot, accounting for the subtraction rank+1. The recursive segment is nonempty in either branch that takes it, and its length strictly decreases. Induction on segment length therefore proves the returned value is the requested order statistic, with at most one recursive call. Only the selected segment is permuted; all outside entries remain unchanged. This is Quickselect.

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

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.