int GroupOfNumbers::linearSelect(int left, int right, int k) { if(left + CutOff <= right) { int pivot = median_of_median_of_5(left, right); int i = left, j = right; for(;;) { while(_group[++i] < pivot && i <= right){} while(_group[--j] > pivot && j >= left){} if(i < j) swap_numbers(i, j); else break; } swap_numbers(i, right); if(k <= i) return linearSelect(left, i, k); else //if(k > i + 1) return linearSelect(i + 1, right, k); } else { insertion_sort(left, right); return(_group[k - 1]); } }