CODEWITHSUNDEEP
algorithmsortingmergemergesortdecision-tree
Riley K
Riley K

Reputation: 403

Creating a decision tree for the mergesort algorithm

In my homework, I need to create the decision tree for n=3 for arbitrary input S={a,b,c}.

Here is my recursive call tree. S={a,b,c} turns into S={a} and S={b,c} and S={b,c} turns into S={b} and S={c}. At the base case, I have S={a}, S={b}, and S={c}.

When I merge S={b} with S={c} I have only 1 decision, check if b < c. If true, S={b,c}. Else, S={c,b}.

Whatever is returned by the previous merge of b and c is merged with S={a}.

In the merge of S={a} and S={b,c}, I have several decisions. I first check if a < b. If true, and since S={b,c} is sorted, S={a,b,c}. If false I have another decision to make. Check if a < c. If true, then S={b,a,c}. Otherwise, S={b,c,a}.

This brings me to my predicament. How do I combine all of my work into a single decision tree? I can create a decision tree for iterative algorithms without any problem, but since this algorithm is recursive, I am confused.

Any help is appreciated. Thanks.

Upvotes: 0

Views: 2547

Answers (1)

rcgldr
rcgldr

Reputation: 28921

You'd have to follow the patch starting at the deepest level of recursion. In this case, the top of the tree is "if (b <= c)". Then if true, as you already mentioned, it's "if (a <= b") S={a,b,c} else "if (a <= c") S = {b,a,c}" "else S = {b, c, a}", then the pattern is similar for when "if (b <= c)" is false.

I'm not sure of the point of this. In the case of n=4, you have 24 possible permutations, for n = 5, 120 permutations, fairly large tree.

Upvotes: 2

Related Questions