in commons-numbers-arrays/src/main/java/org/apache/commons/numbers/arrays/QuickSelect.java [897:951]
private static int repeatedStepFarLeft(double[] a, int l, int r, int k, int[] upper, int flags) {
// Far step has been changed from the Alexandrescu (2016) step of lower-median-of-4, min-of-3
// into the 4th 12th-tile to a min-of-4, median-of-3 into the 2nd 12th-tile.
// The differences are:
// - The upper margin when not sampling is 8/24 vs. 9/24; the lower margin remains at 1/12.
// - The position of the sample is closer to the expected location of k < |A| / 12.
// - Sampling mode uses a median-of-3 with adaptive k, matching the other step methods.
// A min-of-3 sample can create a pivot too small if used with adaption of k leaving
// k in the larger parition and a wasted iteration.
// - Adaption is adjusted to force use of the lower margin when not sampling.
final int fp;
final int s;
int p;
if (flags <= MODE_SAMPLING) {
// 2nd 12th-tile
fp = (r - l + 1) / 12;
s = l + fp;
// Use adaption
p = s + mapDistance(k - l, l, r, fp);
} else {
// i in 2nd quartile; min into i-f (1st quartile)
final int f = (r - l + 1) >> 2;
final int f2 = f + f;
final int end = l + f2;
for (int i = l + f; i < end; i++) {
if (a[i + f] < a[i - f]) {
final double u = a[i + f];
a[i + f] = a[i - f];
a[i - f] = u;
}
if (a[i + f2] < a[i]) {
final double v = a[i + f2];
a[i + f2] = a[i];
a[i] = v;
}
if (a[i] < a[i - f]) {
final double u = a[i];
a[i] = a[i - f];
a[i - f] = u;
}
}
// 2nd 12th-tile
fp = f / 3;
s = l + fp;
// Lower margin has 2(d+1) elements; d == (position in sample) - s
// Force k into the lower margin
p = s + ((k - l) >>> 1);
}
final int e = s + fp - 1;
for (int i = s; i <= e; i++) {
Sorting.sort3(a, i - fp, i, i + fp);
}
p = quickSelectAdaptive(a, s, e, p, p, upper, MODE_FR_SAMPLING);
return expandPartition(a, l, r, s, e, p, upper[0], upper);
}