= Solution
Each recursive call is a <tail call>: nothing remains to be computed after it returns. Replace it by an update of the retained bounds:
``
function Select(i; var a; N): T
require 1 <= i <= N
target := i-1
l := 0
r := N
while true do
Partition(a,l,r,m,n)
if target < m then
r := m
else if target >= n then
l := n
else
return a[target]
``
The <loop invariant> retains the target <order statistic> in $[l,r)$ with $l\leq target<r$. Each nonreturning iteration strictly decreases $r-l$, because $[m,n)$ is nonempty. This proves termination and replaces recursive stack space by \b[$O(1)$ auxiliary space], apart from the pivot routine's own storage.
Back to article page
