快速排序

//We chose pivot
//All elements samller than pivot on the left
//All elements greater than pivot on the right
//Pivot doesn't have to end at its right full position after partition

//pueden pasarse el pivot hasta que ambos punteros se encuentren

//RUN TIME: O(Nlog(N)) -- on average (depends on pivot we chose)
//SPACE COMPLEXITY : null

public class Solution{

  public static void quickSort(int[] array){
    quickSort(array, 0, array.length-1);
  }

  public static void quickSort(int[]array, int left, int right){
    if(left >= right){
      return;
    }

    int pivot = array[(left + right)/2];
    int index = partition(array, left, right, pivot);
    quickSort(array, left, index-1);
    quickSort(array, index, right);
  }

  public static int partition(int[] array, int left, int right, int pivot){

    while(left < right){
      while(array[left]<pivot){
        left ++;
      }

      while (array[right] > pivot){
        right--;
      }

      if(left <= right){
        swap(array, left, right);
        left++;
        right--;
      }
    }

    return left;
  }
}