Implementation of Quick sort using strategy explained by Dr. Rob Edwards from San Diego State University - https://www.youtube.com/watch?v=ZHVk2blR45Q . A good asymptotic analysis of quick sort can be found here https://www.youtube.com/watch?v=-qOVVRIZzao

QuickSort.java

import java.util.Arrays;

public class QuickSort 
{
	static int partitionCounter = 0;
	
	public static void main(String[] args) 
	{
		// Test cases
		// 1. Unsorted array with event no. of elements
		//int arr[] = {7,1,3,9,8,4,16,10};
		
		// 2. Unsorted array with odd no. of elements 
		// int arr[] = {9,4,3,12,19};
		
		// 3. Sorted array with event no. of elements
		 int arr[] = {1,2,3,4,5,6};
		
		// 4. Sorted array with odd no. of elements
		//int arr[] = {1,2,3,4,5};
		
		// 5. Reverse sorted array with event no. of elements
		//int arr[] = {6,5,4,3,2,1};
		
		// 6. Reverse sorted array with odd no. of elements
		//int arr[] = {6,5,4,3,2};
		
		qsort(arr, 0, arr.length-1);
		
		System.out.println("Sorted Array :"+ Arrays.toString(arr));
	}
	
	private static void qsort(int[] arr, int l, int r) 
	{
		// guard against bad inputs
		if (arr == null || arr.length == 1 || l < 0 || r < 0) 
		{
			return;
		}
		
		// boundary condition met
		// end recursion
		if (l >= r)
		{
			return;
		}

		System.out.println("======= Start of partitioning run [" + (++partitionCounter) + "] ========");
		
		int pivotIndex = partition(arr, l, r);
		
		System.out.println("Index of Pivot element at the end of partitioning :"+ pivotIndex);
		
		qsort(arr, l, pivotIndex-1);
		qsort(arr, pivotIndex+1, r);
	}

	
	private static int partition(int[] arr, int l, int r) {
		// take the middle element as pivot.
		int pivotIndex = (l+r)/2;
		int pivotValue = arr[pivotIndex];

		System.out.println("Before partitioning " + Arrays.toString(Arrays.copyOfRange(arr, l, r+1)));
		System.out.println("l=" + l + ", r=" + r + ", p="+ pivotIndex + ", pivot=" + pivotValue);
		
		// move the pivot element to the end of the array
		// This will help in simplify the partitioning algorithm 
		swap(arr, pivotIndex, r);
		// update the pivot index to r
		pivotIndex = r;
		System.out.println("After placing pivot element at the end of array " + Arrays.toString(Arrays.copyOfRange(arr, l, r+1)));
		
		// We need two pointers for partitioning.
		// 1. first pointer points to the next element which is larger than pivot.
		// 2. second pointer is used to scan elements from left to right for partitioning.
		int largerThanPivotIndex = l;
		int currentElementIndex = l;
		
		while (currentElementIndex < r) 
		{
			if (arr[currentElementIndex] < pivotValue) 
			{
				// when we find an element smaller than pivot
				// swap it with the element larger than pivot
				swap(arr, currentElementIndex, largerThanPivotIndex);
	
				// increment this pointer to point to the next element
				// which is larger than pivot. It will be the very next element because
				// any smaller element at that position would have been swapped by this time.
				largerThanPivotIndex++;
			}
			
			// continue processing next element.
			currentElementIndex++;
		}
		
		// At the end of a partitioning run
		// pivot will still be at the end of the array.
		// swap pivot with the next element greater than pivot.
		// Now pivot is at its final position.
		swap(arr, largerThanPivotIndex, pivotIndex);
		
		System.out.println("Result of partition " + Arrays.toString(Arrays.copyOfRange(arr, l, r+1)));
		
		return largerThanPivotIndex;
	}
	
	
	private static void swap(int[] arr, int l, int r)
	{
		int t = arr[l];
		arr[l] = arr[r];
		arr[r] = t;
	}

}

Simplified and more readable version of quick sort.

import java.util.Arrays;

public class QSort2 {

public static void main(String[] args) {
	int arr[] = {11,12,13,14,15,16,17,10};
	sort(arr, 0, arr.length-1);
	
	System.out.println("Sorted Array :"+ Arrays.toString(arr));
	
	int arr2[] = {6,5,4,3,2};
	sort(arr2, 0, arr2.length-1);
	
	System.out.println("Sorted Array :"+ Arrays.toString(arr2));
}

static void sort(int[] arr, int l, int r) {
	if (l < r) 
	{
		int p = partition(arr, l, r);
		
		sort(arr, l, p-1);
		sort(arr, p+1, r);
	}
}

static int partition(int arr[], int l, int r) {
	// Take last element as pivot.
	int pivotIndex = r;
	int pivot = arr[pivotIndex];
	// This is a special variable that will keep track of the first
	// element from the left of the array that is greater than the pivot.
	int indexOfFirstElementGreaterThanPivot = l;
	
	for(int i=l;i<r;i++) {
		if(arr[i] <= pivot) {
			// When you find an element smaller than pivot
			// exchange it with first element greater than pivot.
			swap(arr, i, indexOfFirstElementGreaterThanPivot);
			indexOfFirstElementGreaterThanPivot ++;
		}
	}
	
	// position pivot at the right place by swapping it with
	// first element greater than pivot.
	swap(arr, indexOfFirstElementGreaterThanPivot, pivotIndex);
	int newPivotIndex = indexOfFirstElementGreaterThanPivot;
	
	return newPivotIndex;
}

static void swap(int[] arr, int i, int j) {
	int t = arr[i];
	arr[i] = arr[j];
	arr[j] = t;
}

}