Talk:Quickselect

Overlap with selection algorithm

Some overlap with this and selection algorithm, in particular the section describing this algorithm. Merge out? Dcoetzee 00:04, 18 August 2007 (UTC)

Precise analysis of the expected time of this algorithm

The expected number of comparisons made by this algorithm, when used (with random pivots) to compute the median, is $n(2+2\log 2+o(1))$; see http://11011110.livejournal.com/119720.html. (Perhaps it would be too much of a conflict of interest for me to add this link myself.) Probably somewhere we should mention the related but more complicated algorithm that finds a sample of about square root of the input size, recurses in the sample, and uses the result as a pivot, getting $n+\min(k,n-k)+O(n^{1/2})$ comparisons in expectation. —David Eppstein (talk) 23:35, 22 August 2013 (UTC)