//QuickSort(A[], p, r)
//  if p < r
//      q = Partition(A[], p, r)
//      QuickSort(A[], p, q - 1)
//      QuickSort(A[], q + 1, r)

public static void QuickSort(int[] integerArray, int lowIndex, int highIndex) {
	if (lowIndex < highIndex) {
		int mid = Partition(integerArray, lowIndex, highIndex);
		QuickSort(integerArray, lowIndex, mid - 1);
		QuickSort(integerArray, mid + 1, highIndex);
	}
}

//Partition(A[], p, r)
//  x = A[r]
//  i = p - 1
//  for j = p to r - 1
//      if A[j] <= x
//          i = i + 1
//          exchange A[i] with A[j]
//exchange A[i + 1] with A[r]
//return i + 1

public static int Partition(int[] integerArray, int lowIndex, int highIndex) {
	int pivot = integerArray[highIndex];
	int i = lowIndex - 1;
	int temp;
	for (int j = lowIndex; j < highIndex; j++) {
		if (integerArray[j] <= pivot) {
			i++;
			temp = integerArray[i];
			integerArray[i] = integerArray[j];
			integerArray[j] = temp;
		}
	}
	temp = integerArray[i + 1];
	integerArray[i + 1] = integerArray[highIndex];
	integerArray[highIndex] = temp;

	return i + 1;
}