The quick sort partitions objects into two groups, one group of the objects with a value above a certain value, and another group with a value below.  Each of these groups is further divided, and this action continues recursively until the array is sorted.

For example, if we have an array of numbers [23, 4, 10, 9, 6, 12, 17]:

Using 10 as the pivot value, we sort the arrays into two groups (with the pivot value in the middle)

[ 4, 9, 6]     [10]     [23, 12, 17]

Then we apply the same process to the left group pivoting around 6:

[4]  [6]  [9]

and around 17 in the right group:

[12] [17] [23]

Putting it all together, the array is sorted.

The question in implementation comes in deciding which value within the array to use as the pivot.  The ideal scenario is choosing the number in the middle of the array (as I did above), but until the array is sorted, we can’t know which number is in the middle (consider an array of 10,000 numbers instead of 7).

Choosing the leftmost element in the array seems as good as any, but what would happen if the array was already sorted, or at least mostly sorted?

Starting with 4,6,8,7,10,12,11

Pivoting around 4, there are no elements in the left array:

[4]    [6,7,8,10,11, 12,14]

Then pivoting around 6 does no better.

[4]   [6]  [8,7,10,11,12,14]

So in this case, choosing the leftmost value as the pivot leads to the worst case for this algorithm, O(n^2). It takes O(n) time to compare each element to the pivot, and we have to perform this algorithm n times (once for each item in the array).

As we increase the number of elements in the array, the amount of time it takes to sort increases quadratically.    That is not good, so if you expect your arrays to be mostly sorted, quick sort is probably not for you.

In the best case scenario, when we choose the middle element as the pivot for each operation each partition operation still takes  O(n).  To see how many sorts we will need, consider that each sublist is half the size of the main list.  We are only sorting until the size of the sublists get to 1.  So how many times must you divide a number by 2 until it gets to 1?  Put another way, how many times must we double the number 1 until we exceed the number of elements in the array?  That is the definition of a logarithm,( the exponent of 2 that will equal a given number.  Log(8) = 3  because 2^3 = 8 ).  So we need to perform log(n) recursions, and the total efficiency of the algorithm turns out to be O(nlog(n))

There are many variations of this algorithm, for example, partitioning the array in place instead of in new arrays, reducing the memory requirements.  Others have to do with how you choose the pivot element.  For example, you could choose a small number of items from the list and take the median of this selection as the pivot.  Understanding the data you are trying to sort – what will it likely look like when you want to sort it, will help you implement a quicksort in the most efficient manner.

Below is a basic implementation in java, using the value in the center of the array as the pivot:

/**
	 * Sorts the input array list from lowest to highest using the quick sort algorithm
	 * Written By Aaron Zimmerman
	 * http://www.algorithmatica.com
	 * @param the list to be sorted
	 * @return the sorted array
	 */ 
	public static ArrayList<Integer> quicksort(ArrayList<Integer> data){
		
		if (data.size() <= 1){
			return data; //array is sorted
		}
		int pivot = data.size() / 2;
		Integer pivotValue = data.remove(pivot);
		ArrayList<Integer> less = new ArrayList<Integer>();
		ArrayList<Integer> more = new ArrayList<Integer>();
		
	  for(Integer item : data){
		  if (item <= pivotValue){
			  less.add(item);
		  } else {
			  more.add(item);
		  }
	  }
	  
	  ArrayList<Integer> returnList = new ArrayList<Integer>();
	  returnList.addAll(quicksort(less));
	  returnList.add(pivotValue);
	  returnList.addAll(quicksort(more));
	  
	  return returnList;
	
		
	}