that the 4 3-way Merge Sort Consider the natural 3-way extension of merge sort: function mergesort3(A) if len(A) S 1: return A Al mergesort3(A[1.n/3) A2 mergesort3(A[n/3+1.2/3n]) A3 mergesort3(A[2/3n+1.) return merge3(A1,A2,A3) (The merge3 function is defined similarly to the usual merge function, except now it uses three fingers.) Is mergesort3 faster than the normal merge sort? Let's find out! (It may be helpful to draw the tree asked for in part e as you answer parts a-d. (a) What is the branching factor of mergesort3's recursion tree? (b) What is the factor by which a child node's problem instance size shrinks compared to its parent's problem instance size? (c) What is the height of mergesort3's recursion tree? (Indicate the base of any logs involved.) (d) How many nodes are there on layer & of mergesort3's recursion tree (in the worst case)? (e) Approximately how many comparisons (including an estimate of the hidden big-0 coefficient if possible) are performed by the natural merge3(A1,A2,A3) subroutine, as a function of its input size (i.e., n- len(A1)+len(A2)+len(A3)) in the worst case