private static <T extends Comparable<T>> int
partition(T array[], int left, int right) {
// Permute the non-empty array segment array[left..right - 1] so that, for
// some left <= mid < right, array[left..mid - 1] <= array[mid] < array[mid
// + 1..right - 1]. Return mid.
assert left < right;
final int l = left++;
final T pivot = array[l];
// array[left .. left - 1] <= pivot < a[right .. right' - 1]
while (left < right)
if (pivot.compareTo(array[left]) >= 0)
left++;
else if (pivot.compareTo(array[right - 1]) < 0)
right--;
else
swap(array, left++, --right);
swap(array, l, --left);
return left;
}