code: public static <E extends Comparable<E>> int partition(List<E> array, int left, int right) {
      final int mid = left + ((right - left) / 2);
      E pivot = array.get(mid); // taking mid point as pivot
  
      while (left <= right) {
        //searching number which is greater than pivot, bottom up
        while (array.get(left).compareTo(pivot) < 0) {
          left++;
        }
        //searching number which is less than pivot, top down
        while (array.get(right).compareTo(pivot) > 0) {
          right--;
        }
  
        // swap the values
        if (left <= right) {
          E tmp = array.get(left);
          array.set(left, array.get(right));
          array.set(right, tmp);
  
          //increment left index and decrement right index
          left++;
          right--;
        }
      }
      return left;
    }
docs: Divides array from pivot, left side contains elements less than
  Pivot while right side contains elements greater than pivot.
  
  @param array array to partitioned
  @param left  lower bound of the array
  @param right upper bound of the array
  @param <E>   generic type of list
  @return the partition index