Question: We've seen a number of sorting algorithms in the last few weeks: selection sort, insertion sort, mergesort, quicksort, and heapsort. Describe the advantages and disadvantages of each.
Answer: You may not think of everything. The items below that are particularly advanced are italicized. Pages 572-574 of the textbook include a nice comparison of sorting techniques.
Selection sort is among the simplest algorithms to implement. It is very easy to verify if it is correct, and so a programmer is more likely to implement it correctly than other algorithms.
Selection sort also performs the least data movement of any of the algorithms.
The problem with selection sort is that its worst case is extremely poor.
Insertion sort's primary advantage is that its best case is O(n), when the list is already sorted. When the list is nearly sorted, it also does quite well, making it the list of choice when we have an array that's likely to have changed very little since it was last sorted.
Unfortunately its worst case is quite poor.
We do not know a way to implement mergesort without creating another array into which to place the merged array. This allocation of another array and copying elements to it can be quite expensive.
On the other hand, mergesort has good worst-case performance. The number of comparisons it performs is optimal in the largest-order term. (It takes at most n log_2 n - n + 1 comparisons.)
Quicksort does well in theory and it is the best sorting technique in practice when comparisons are relatively cheap (such as in comparing integers or strings).
The primary disadvantage with quicksort is that its absolute worst case is O(n^2). If we choose the pivot points randomly, we can guarantee that this behavior is unlikely, but we cannot provide an absolute guarantee.
Heapsort is good when we want a fast technique that absolutely guarantees O(n log n) time. Mergesort, the other technique that guarantees this, is slower in practice because it must create a second array.
Heapsort may make more comparisons than optimal. Each siftUp operation makes two comparisons per level, so the comparison bound is approximately 2n log_2 n. In practice heapsort does only slightly worse than quicksort.