1. 23

  2. 3

    In the postscript a 2017 paper is mentioned that describes QuickselectAdaptive, which is then shown to be even faster.

    In order to implement adaptation, we need to dynamically choose the partitioning algorithm from among MedianOfMinima, MedianOfNinthers, and MedianOfMaxima. A good place to decide strategy is the Quickselect routine itself, which has access to the information needed and drives the selection process. Before each partitioning step, the appropriate partitioning algorithm is chosen depending on the relationship between |A| and k. After partitioning, both A and k are modified and a new decision is made, until the search is over. QuickselectAdaptive (Algorithm 8) embodies this idea.

    The C++ source code for all of the algorithms mentioned in the paper are available here from the author. What’s exciting about this new selective algorithm is that its performance brings deterministic selection (along with its desirable properties of reproducible runs, predictable run times, and immunity to pathological inputs) into practicality with varying uniformity of input values.