public class Solution {
  public int[] quickSort(int[] array) {
    // Write your solution here
    if (array == null || array.length == 0) {
      return array;
    }
    helper(array, 0, array.length - 1);
    return array;
  }

  private void helper(int[] array, int start, int end) {
    if (start > end) {
      return;
    }
    int left = start;
    int right = end;
    int pivot = array[(left + right) / 2];
    while (left <= right) {
      while (left <= right && array[left] < pivot) {
        left++;
      }
      while (left <= right && array[right] > pivot) {
        right--;
      }
      if (left <= right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
        left++;
        right--;
      }
    }
    helper(array, start, right);
    helper(array, left, end);
  }
}