Sorting

1. You are given an array with 100,000 entries to sort. Under what circumstances would you use each of the following:

   1. insertion sort

   2. mergesort

   3. quicksort

2. A list of five characters, 'a', 'b', 'c', 'd', and 'e', is stored in an array. Give a starting arrangement of these characters that would result in mergesort making the most number of comparisons to sort the list. Show the mergesort recursion tree, as well number of comparisons for each merge, otherwise you will not get any credit. Also, if your answer is not the worst case, you will NOT get ANY credit, even if the process is correctly described. (Assume that a split on an odd number of entries results in one extra entry in the left half.)