In the lectures and in the notes, we examined the exact worst-case cost of sorting five items using two different sorting algorithms: MergeSort, and an ad hoc optimal algorithm for sorting exactly five items. In this problem, you are being asked to give the exact cost of sorting five items using other approaches. In all parts of this problem, cost means the number of comparisons performed between two input items.

(a) What is the exact worst-case cost of sorting five items using insertion sort?

(b) What is the exact worst-case cost of sorting five items using QuickSort?

(c) What is the exact expected cost of sorting five items using QuickSort, assuming all 5! permutations are equally likely. (For this part, it is fine to use a calculator or write and run a computer program.)