Question

Problem 1 (4+3 marks). (a) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Mergesort. Count the number of comparisons made. (b) Illustrate how the list 5, 13, 2, 25, 7, 17, 20, 8, 4 is sorted with Heapsort.

Answer 1

1)Merge sort illustration.

5, 13, 2, 25, 7, 17, 20, 8, 4
divide it into two parts
5 13 2 25 7 17 20 8 4
divide each part into two parts
5 13 2 25 7 17 20 8 4

divide each part into one part ,except for 20,8 and 4.Here divide 20 from 8 and 4.

5 13 2 25 7 17 20 8 4
Again divide 8 and 4 into two parts
5 13 2 25 7 17 20 8 4

merge parts
5 13 2 25 7 17 20 4 8
Merging again
5 13 2 25 7 17 4 8 20

merge parts
2 5 13 25 4 7 8 17 20
merge parts into one
2 4 5 7 8 13 17 20 25

2)Heapsort illustration.

A=〈5,13,2,25,7,17,20,8,4〉.
〈5,13,2,25,7,17,20,8,4〉
〈5,13,20,25,7,17,2,8,4〉
〈5,25,20,13,7,17,2,8,4〉
〈25,5,20,13,7,17,2,8,4〉
〈25,13,20,5,7,17,2,8,4〉
〈25,13,20,8,7,17,2,5,4〉
〈4,13,20,8,7,17,2,5,25〉
〈20,13,4,8,7,17,2,5,25〉
〈20,13,17,8,7,4,2,5,25〉
〈5,13,17,8,7,4,2,20,25〉
〈17,13,5,8,7,4,2,20,25〉
〈2,13,5,8,7,4,17,20,25〉
〈13,2,5,8,7,4,17,20,25〉
〈13,8,5,2,7,4,17,20,25〉
〈4,8,5,2,7,13,17,20,25〉
〈8,4,5,2,7,13,17,20,25〉
〈8,7,5,2,4,13,17,20,25〉
〈4,7,5,2,8,13,17,20,25〉
〈7,4,5,2,8,13,17,20,25〉
〈2,4,5,7,8,13,17,20,25〉
〈5,4,2,7,8,13,17,20,25〉
〈2,4,5,7,8,13,17,20,25〉
〈4,2,5,7,8,13,17,20,25〉
〈2,4,5,7,8,13,17,20,25〉