Problem 1. Consider an array consisting of 17, 20, 8, 19, 42, 34, 6, 13

Do NOT answer with code, show all the steps of the algorithm by hand, and count the total comparisons.

a) Sort via Mergesort in increasing order showing ALL work and give EXACT number of comparisons

b) Sort via Quicksort using Split with the first element of each subarray as the pivot. Show ONLY the first stage of Split to find the correct location of A[1] but give the EXACT number of comparisons to sort completely, no need to show intermediate stages.

c) Sort via Heapsort as explained in class, and give the EXACT number of comparisons. FIRST, build heap using heap structure. Show work.