public class QuickSort {

public static void QuickSort(int[] arr) {
   recQuickSort(arr, 0, arr.length-1);
}


public static void recQuickSort(int[] arr, int left, int right){
   if (right - left <= 0) return;
   else {
      int border = partition(arr, left, right);
      recQuickSort(arr, left, border-1);
      recQuickSort(arr, border+1, right);
   }
}

public static int partition(int[] arr, int l, int r) {

   int pivot = arr[r]; // choose the last element as the pivot
   int red = l;  // set at the left border of the range
   int blue = r; //set at the right border where the pivot sits
   int temp;

   while(red < blue) {
      if (arr[red] < pivot) red++;
      else {
         blue--;
         temp = arr[red];
         arr[red] = arr[blue];
         arr[blue] = temp;            //swap(arr, red, blue)
      }
   }
   temp = arr[r];
   arr[r] = arr[blue];
   arr[blue] = temp;                 //  swap(arr, blue, r)
                                     // (put the pivot on the border)
   return blue;
}

public static void main(String[] args) {
   int[] arr = {6,7,3,4,5};
   QuickSort(arr);
   for (int i = 0; i < arr.length; i++) {
       System.out.print(arr[i] + " ");
   }
   System.out.println();
}

}