Question

Consider the following array: 2, 13, 16, 3, 7, 23, 12, 25. Show a trace of execution for top-down mergesort using the method shown in lecture (where both sides are updated at once). Illustrate how the array is broken down, and then merged into an ordered state.

does this look correct?

1 (initial): [2, 13, 16, 3, 7, 23, 12, 25]

2 (down): [[2, 13, 16, 3],[7, 23, 12, 25]]

3 (down): [[[2, 13], [16, 3]],[[7, 23], [12, 25]]]

4 (mid): [[[[2], [13]], [[16], [3]]],[[[7], [23]], [[12], [25]]]]

5 (up): [[[2, 13], [3, 16]],[[7, 23], [12, 25]]]

6 (up): [[2, 3, 13, 16],[7, 12, 23, 25]]

7 (up): [2, 3, 7, 12, 16, 23, 25]

Answer 1

Ans: Yes, according to the question where it is said, both sides are updated at once, the answer given by you is perfect. In merge sort, first array is divided in two sections until we get arrays of single element, and after that those arrays are merged in such an order that every new array by combining two array is sorted

1(Initial): [2, 13, 16, 3, 7, 23 , 12, 25]

2(down): [[2, 13, 16,3],[7, 23, 12, 25]]

3(down): [[[2,13],[16, 3]], [[7, 23], [12,25]]]

4 (mid): [[[[2], [13]], [[16], [3]]],[[[7], [23]], [[12], [25]]]]

5 (up): [[[2, 13], [3, 16]],[[7, 23], [12, 25]]]

6 (up): [[2, 3, 13, 16],[7, 12, 23, 25]]

7 (up): [2, 3, 7, 12, 16, 23, 25]