TOPIC 19.3.1
Analyzing and Choosing the Right Sort

Below is a summary of the performance of each sort, and when it is best to use each sort.

A common analyzation technique, big-O notation, is used to analyze the speed of these sort algorithms.  If you are not familiar with big-O notation, refer to Appendix E (page 445).

Quick Sort:

The worst case behavior of the quick sort is when unbalanced partitioning arises at every step of the algorithm. The best case behavior of the quick sort is when the partitioning procedure produces two regions of equal size. On average, the quick sort has a big O running time of O(n*ln(n)), which is very close to the best case and is very efficient.

Merge Sort:

The merge sort works best when the number of elements is a power of 2. The big O running time is O(n*ln(n)). One disadvantage of the merge sort is that it requires extra memory to maintain an array equal in size to the array you are sorting.

Insertion Sort:

Insertion sort is most efficient for sorting a small number of elements. The big O running time is O(n^2).

Selection Sort:

The selection sort is one of the easiest sorts to implement, but is among the least efficient.

Bubble Sort:

One good aspect of the bubble sort is that it provides a way to end early. The big O running time is O(n^2).

Shell Sort:

The worst case behavior of the shell sort is when the list is in reverse order. The best case results when the list is nearly sorted. On average the shell sort has a big O running time of O(n^2) which is close to the worst case.

Summary:

Big O of O(n^2) sorts usually have the best case result when the data is already in order and when the list is relatively small. The worst case usually results when the data is in reverse order. While sorts with a big O of O(n*ln(n)) sorts are most efficient on large lists.