private static <T extends Comparable<T>>
    int partition(T[] list, int lo, int hi) {
        T pivot = list[lo];
        int left = lo + 1;
        int right = hi;

        while (true) {
            while (left <= right) {
                if (list[left].compareTo(pivot) < 0) {
                    left++;
                } else {
                    break;
                }
            }

            while (right > left) {
                if (list[right].compareTo(pivot) < 0) {
                    break;
                } else {
                    right--;
                }
            }

            if (left >= right) break;

            T tmp = list[left];
            list[left] = list[right];
            list[right] = tmp;
            left++; right--;
        }

        list[lo] = list[left - 1];
        list[left - 1] = pivot;

        return left - 1;
    }