9. Quicksort

This algorithm was developed back in 1962 as an extremely fast way of sorting medium to large lists. It is a type of merge sort.

The basic idea is to keep splitting a list into two smaller lists, sort those lists using the same quicksort rules, then split the sub-lists and sort again, until there are only lists of 1 item or less left.

The basic algorithm works like this

1. If the list to be sorted is length 1, then finish - job complete
2. Pick an item within the list to act as a 'pivot'. The left-most item is a popular choice.
3. Split the list into two parts - one list with items equal to or larger than the pivot item and the other list contains items smaller than the pivot
4. Repeat this process on the two halves

This is very similar to the merge sort procedure except the pivot can be applied to any item in the unsorted list.

Points to note.

Quicksort relies heavily on recursion - each split is usually a subroutine call within a program. And one of the problems of recursion is that the stack can grow so much that a stack overflow occurs. So one of the issues to be careful about is that the original list is not so large that the computer runs out of stack memory before the sort is complete.

Quicksort does not work well with sorted lists when the left most item is chosen as a pivot. If this is the case, then it is better to pick another pivot point at random.

Very complex algorithm to code - the four steps seem simple, but the deep recursion makes it difficult to code. If you only need to sort a small list the one time, then the work involved in coding a quicksort is not worthwhile.