import java.util.Arrays;

public class QuickSort {

public static void sort(Integer[] nums) {

quicksort(nums, 0, nums.length - 1);

}

public static void quicksort(Integer[] nums, int left, int right) {

if (left < right) {

int pivot = partition(nums, left, right);

quicksort(nums, left, pivot - 1);

quicksort(nums, pivot + 1, right);

}

}

public static int partition(Integer[] nums, int left, int right) {

int pivotIndex = (left + right - 1) / 2;

int pivotVal = nums[pivotIndex];

while(true) {

while (nums[left] < pivotVal) {

left++;

}

while (nums[right] > pivotVal) {

right--;

}

if ( left >= right) {

return right;

}

// swap

int temp = nums[left];

nums[left] = nums[right];

nums[right] = temp;

}

}

}