in commons-numbers-arrays/src/main/java/org/apache/commons/numbers/arrays/QuickSelect.java [1692:1720]
static void sortSelectLeft(int[] a, int left, int right, int k) {
// Sort
for (int i = left; ++i <= k;) {
final int v = a[i];
// Move preceding higher elements above (if required)
if (v < a[i - 1]) {
int j = i;
while (--j >= left && v < a[j]) {
a[j + 1] = a[j];
}
a[j + 1] = v;
}
}
// Scan the remaining data and insert
// Mitigate worst case performance on descending data by backward sweep
int m = a[k];
for (int i = right + 1; --i > k;) {
final int v = a[i];
if (v < m) {
a[i] = m;
int j = k;
while (--j >= left && v < a[j]) {
a[j + 1] = a[j];
}
a[j + 1] = v;
m = a[k];
}
}
}