2 Decision Tree Models (40 points) In class, we have used the decision tree model to derive a lower bound for the worst-case running time of comparison-based sorting, including insertion sort, merge sort, heapsort and quicksort. 2.1 Mergesort (10 points ) Given an input sequence with 2 elements: [a1,Q2 ], where a1 t a2. Draw the decision tree model for Mergesort running on this sequence. 2.2 Heapsort (10 points) Given an input sequence with 8 elements: (a1, 2, a3, a4, a5, af, a7, a8), where all the elements are distinct from each other. For the decision tree model for Heapsort running on this input sequence, what is the root node of your decision tree model? 2.3 Insertionsort (10 points) Given an input sequence with 8 elements: a1, a2, a3, a4, a5, a6, a 7, ag), where all the elements are distinct from each other. For the decision tree model for Insertionsort running on this input sequence, what is the root node of your decision tree model? 24Quicksort (10 points ) Given an input sequence with 8 elements: [a1, a2, a3, a4, a5, af, a7, as), where all the elements are distinct from each other. For the decision tree model for Quicksort running on this input sequence, what is the root node of your decision tree model