quicksort

class Solution {
  /**
   * @param elements
   *     Array of integers to be sorted.
   */
  public static void quickSort(int[] elements) {
    if(elements == null || elements.length < 2) {
      return;
    }
    sort(elements, 0, elements.length-1);
  }

  public static void sort(int[] arr, int low, int high) {
    if (high > low) {
      int pos = partition(arr, low, high);
      sort(arr, low, pos-1);
      sort(arr, pos+1, high);
    }
  }
  public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low-1;

    for(int j = low; j < high; j++) {
      if (arr[j] < pivot) {
        i++;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
    int temp = arr[i+1];
    arr[i+1] = arr[high];
    arr[high] = temp;

    // for(int j = 0; j < arr.length; j++) {
    //   System.out.print(arr[j] + ", ");
    // }
    // System.out.print(i+1);
    // System.out.println();
    return i+1;
  }
}