Question 3 - Understanding Merge Sort (15 points) Consider the merge sort algorithm we learned in Lessons and 9 void Mergesort(std::vectorcint avec, int left, int right if (left (right) { int mid - (left + right)/ 2; MergeSort(vec, left, mid); Mergesort (vec, mid + 1, right); Merge(vec, left, mid, right); > } a) 2 points) Merge sort is a divide-and-conquer algorithm. What is the divide step of the algorithm? (b) (2 points) Merge sort is a divide-and-conquer algorithm. What is the "conquer" step of the algorithm (c) (2 points) Let's say we call MergeSort on the vector {1, 2, 3, 4, 5, 6, 7, 8). How many times will MergeSort be called in total, including the initial call? Hint: It may help to draw a diagram of the splits or reference the example from the Lesson 9 slides. (d) (2 points) Let's say we call MergeSort on the vector {1, 2, 3, 4, 5, 6, 7, 8). What is the maximum number of MergeSort stack frames that will be on the call stack at any given point in time? In other words, what is the height of the recursive call tree? (e) 3 points) What is the best case time complexity of MergeSort? What is the worst case time complexity? Are these the same or different, and why? ( (4 points) Now, consider the Merge function we wrote together in class. (You may reference the slides from Lesson 8 or Lesson 9 or this Repl.it: https://replin@KarenslessonSmergesort). Let's say we call the Merge algorithm on the vector (2, 4, 1, 3) (with left -0, mid-1, and right - 3) () How many times will the first while loop iterate? while (left_index