Problem 1. 1. Draw the decision tree for the merge-sort algorithm for the input

Question

Problem 1.

1. Draw the decision tree for the merge-sort algorithm for the input consisting of 3 numbers: a, b,c.

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.

Explanation / Answer

part-1:

let left part in merge sort is from 0 to mid and right part is from mid+1 to high.

Where mid = (low+high)/2 , low = 0 and high = n-1 in starting

so if the array has 3 elements then it will be divided into two parts left and right, where the left has only one element => so can't divide further but right has 2 elements => will be divided again

The tree is as follow:

root(a,b,c)

left child only one element

right child 2 elements

left child of the right child

right child of the right child

Part2:

The tree is as follow:

root(a,b,c,d)

left child 2 elements

left child of the left child

right child of the left child

right child 2 elements

left child of the right child

right child of the right child

Part-3:

According to tree shown in part-1 and part-2, in the part-1 tree has 3 leaves and in the part-2 tree has 4 leaves.

Part-4:

As shown tree in part-1 and part-2, both trees have 3 levels.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.