private int partition(int[] input, int lo, int hi) {
        int left = lo;
        int right = hi + 1;

        while (true) {
            while (input[++left] < input[lo]) {
                if (left == hi) break;
            }

            while (input[--right] > input[lo]) {
                if (right == lo) break;
            }
            if (right <= left) break;
            exchange(input, right, left);
        }
        exchange(input, lo, left);

        return left;

    }