4.1: There are two parts to this problem (HW4.1A,HW4.1B) 4.1A: Draw the decision tree for Mergesort (Algorithm 4.5, Page 175), which uses Merge (Algorithm 4.4, Page 172) when n=3. To get this right, you'll have to carefully examine the code at the bottom of page 175; remember that array numbering starts at index zero, and that integer division *truncates* (it doesn't round). 4.1B: Based on *your* decision tree in 4.1A, determine the average number of comparisons done by Mergesort when n=3. (Do NOT try to plug into some formula; I am simply asking you to examine your decision tree and count the number of comparisons, taking a weighted average to find the exact answer.)

page # 175

page # 172

This is the similar diagram on page 178, but the one needed to be drawn is slightly different:

The solution would be exactly what you need if you add the decision tree diagram mentioned in the problem.

Algorithm 4.5 Mergesort Input: Array E and indexes first, and last, such that the elements of Elil are defined for first si last. Output: Elfirst],..., Ellast] is a sorted rearrangement of the same elements. 2 void mergeSort(Element[] E, int first, int last) if (first