Quicksort
Quicksort is a very efficient sorting algorithm invented by C.A.R. Hoare. It has two phases:
 the partition phase
 the sort phase
Most of the work is done in the partition phase  it works out where to divide the work. The sort phase simply sorts the two smaller problems that are generated in the partition phase.
This makes Quicksort a good example of the divide and conquer strategy for solving problems. This is similar in principle to the binary search. In the quicksort, we divide the array of items to be sorted into two partitions and then call the quicksort procedure recursively to sort the two partitions, ie we divide the problem into two smaller ones and conquer by solving the smaller ones.
Click here for an animation of the quicksort algorithm from CS Animation
The conquer part of the quicksort routine looks like this:
1 2 3 4 5 6 7 8 

The divide part of the algorithm looks like this in Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 

Exercises
 Download an implemented version of the quicksort program and test that it works.
 Extend this program by adding a counter to count the number of comparisons.
 Compare your count with the insertion sort (next page) to see which is the most efficient sort.
 Previous  Insertion Sort
 Next  Stacks