Problem 1.

2. Draw the 4 top levels of the decision tree for the merge-sort algorithm for the input consisting of 4 numbers: a, b, c, d

3. How may leaves does this tree have?

4. How many levels does this tree have?

5. What is the number of comparisons needed to sort these 4 numbers by the merge-sort algorithm in the worst case?

6. What is this number in the best case?

7. Is there an algorithm that in the worst case sorts 4 numbers with a smaller number of comparisons? Justify the answers to all these questions.