Jacob Marley

“
Randomized-Select(A, p, q, k) // finds k-th smallest element in array A[p..q]
if p == q
return A[p]
r = Randomized-Partition(A, p, q)
l = r - p + 1
if k == l
return A[r]
if k < l
return Randomized-Select(A, p, r-q, k)
else
return Randomized-Select(A, r+1, q, k-l)
” source...