A list of five characters, \'a\', \'b\', \'c\', \'d\', and \'e\', is stored in a

Question

A list of five characters, 'a', 'b', 'c', 'd', and 'e', is stored in an array. Give a starting arrangement of these characters that would result in mergesort making the most number of comparisons to sort the list. Show the mergesort recursion tree, as well number of comparisons for each merge, otherwise you will not get any credit. Also, if your answer is not the worst case, you will NOT get ANY credit, even if the process is correctly described. (Assume that a split on an odd number of entries results in one extra entry in the left half.)

Explanation / Answer

For worst case, every element in the left and right sub array need to be compared before merging.

Final answer {'a', 'b', 'c', 'd', 'e'}

For worst case, left and right array sub array before merging should be {'a', 'c', 'e'} and {'b', 'd'}

Applying the same logic, for {'a', 'c', 'e'}, for worst comparison left and right array should be { 'a' , 'e'} and {'c'}

When the array is of size 2, definitely 2 elements will be compared, regardless of its order.

Hence, the worst case arrangement is {'a', 'e', 'c', 'b', 'd'}

Input array arr[] = [ 'a', 'e', 'c', 'b', 'd']
/
/
['a', 'e', 'c'] ['b', 'd']
/ |
/ |
['a', 'e'] ['c'] ['b', 'd']
| | |
| | | - Merge step for ['a','e'] and ['b','d'] separately
['a', 'e'] ['c'] ['b', 'd'] 1 comparison for merge of ['a', 'e'] and 1 comparison for merge of ['b', 'd']   
/ |
/ | - Merge of ['a', 'e'] and ['c']
['a', 'c', 'e'] ['b', 'd'] - 2 comparisons
/
/ - Merge of ['a', 'c', 'e'] and ['b', 'd']
[ 'a', 'b', 'c', 'd', 'e'] - 4 comparisons
          
Totally 4 + 2 + 1 + 1 = 8 comparisons at worst case

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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