Hint: Sorting

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.

Hint: In comparing sorting algorithms, here are a few things to consider.

• How simple is the algorithm? For life-dependent systems, it may be preferable to choose the algorithm the programmer is most likely to implement correctly.
• How does it do in the best case? Are there applications where the best case is likely?
• What is the worst case? Are there applications where the worst case is likely?
• How fast is the algorithm in general? Consider big-O notation.
• How many comparisons will the algorithm take? In a tournament environment, each comparison involves a long game and so is very expensive. It is worth considering the exact number of comparisons required.
• Can the algorithm sort without creating another array? When comparisons are cheap, allocating a different array and copying elements over is expensive.

Answer.