Quickselect and its variants are the selection algorithms most often used in efficient real-world implementations.

As with quicksort, quickselect is generally implemented as an in-place algorithm, and beyond selecting the kth element, it also partially sorts the data.

See selection algorithm for further discussion of the connection with sorting.

In quicksort, there is a subprocedure called partition that can, in linear time, group a list (ranging from indices left to right) into two parts: those less than a certain element, and those greater than or equal to the element.

In quicksort, we recursively sort both branches, leading to best-case

Therefore, a single recursive call locates the desired element in the correct partition, and we build upon this for quickselect: Note the resemblance to quicksort: just as the minimum-based selection algorithm is a partial selection sort, this is a partial quicksort, generating and partitioning only

It is also an in-place algorithm, requiring only constant memory overhead if tail call optimization is available, or if eliminating the tail recursion with a loop: Like quicksort, quickselect has good average performance, but is sensitive to the pivot that is chosen.

If good pivots are chosen, meaning ones that consistently decrease the search set by a given fraction, then the search set decreases in size exponentially and by induction (or summing the geometric series) one sees that performance is linear, as each step is linear and the overall time is a constant times this (depending on how quickly the search set reduces).

However, if bad pivots are consistently chosen, such as decreasing by only a single element each time, then worst-case performance is quadratic:

[2] The easiest solution is to choose a random pivot, which yields almost certain linear time.

Deterministically, one can use median-of-3 pivot strategy (as in the quicksort), which yields linear performance on partially sorted data, as is common in the real world.

However, the overhead of computing the pivot is high, and thus this is generally not used in practice.

Finer computations of the average time complexity yield a worst case of

[3] The constant can be improved to 3/2 by a more complicated pivot strategy, yielding the Floyd–Rivest algorithm, which has average complexity of