android/guava/src/com/google/common/math/Quantiles.java
private static void selectInPlace(int required, double[] array, int from, int to) {
    // If we are looking for the least element in the range, we can just do a linear search for it.
    // (We will hit this whenever we are doing quantile interpolation: our first selection finds
    // the lower value, our second one finds the upper value by looking for the next least element.)
    if (required == from) {
      int min = from;
      for (int index = from + 1; index <= to; index++) {
        if (array[min] > array[index]) {
          min = index;
        }
      }
      if (min != from) {
        swap(array, min, from);
      }
      return;
    }

    // Let's play quickselect! We'll repeatedly partition the range [from, to] containing the
    // required element, as long as it has more than one element.
    while (to > from) {
      int partitionPoint = partition(array, from, to);
      if (partitionPoint >= required) {
        to = partitionPoint - 1;
      }
      if (partitionPoint <= required) {
        from = partitionPoint + 1;
      }
    }
  }
private static void selectInPlace(int required, double[] array, int from, int to) {
    // If we are looking for the least element in the range, we can just do a linear search for it.
    // (We will hit this whenever we are doing quantile interpolation: our first selection finds
    // the lower value, our second one finds the upper value by looking for the next least element.)
    if (required == from) {
      int min = from;
      for (int index = from + 1; index <= to; index++) {
        if (array[min] > array[index]) {
          min = index;
        }
      }
      if (min != from) {
        swap(array, min, from);
      }
      return;
    }

    // Let's play quickselect! We'll repeatedly partition the range [from, to] containing the
    // required element, as long as it has more than one element.
    while (to > from) {
      int partitionPoint = partition(array, from, to);
      if (partitionPoint >= required) {
        to = partitionPoint - 1;
      }
      if (partitionPoint <= required) {
        from = partitionPoint + 1;
      }
    }
  }
Performs an in-place selection to find the element which would appear at a given index in a
dataset if it were sorted. The following preconditions should hold:

<ul>
<li>{@code required}, {@code from}, and {@code to} should all be indexes into {@code array};
<li>{@code required} should be in the range [{@code from}, {@code to}];
<li>all the values with indexes in the range [0, {@code from}) should be less than or equal
to all the values with indexes in the range [{@code from}, {@code to}];
<li>all the values with indexes in the range ({@code to}, {@code array.length - 1}] should be
greater than or equal to all the values with indexes in the range [{@code from}, {@code
to}].
</ul>

This method will reorder the values with indexes in the range [{@code from}, {@code to}] such
that all the values with indexes in the range [{@code from}, {@code required}) are less than or
equal to the value with index {@code required}, and all the values with indexes in the range
({@code required}, {@code to}] are greater than or equal to that value. Therefore, the value at
{@code required} is the value which would appear at that index in the sorted dataset.