We are using merge sort to sort the following numbers (1 to 16) 13 9 11 2 7 15 1

Question

We are using merge sort to sort the following numbers (1 to 16)

13 9 11 2 7 15 10 4 16 5 1 8 12 6 3 14

This diagram from Wikipedia http://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg

gives a good idea of the algorithm, but it might give the wrong impression of the order the merge

operations happen as the recursion progresses since it might seem the merges happen in parallel.

Provide below the merges in the correct order together with the state of the array. The last merge should

have the whole array sorted. The first two have been given below to get you started.

9 13 11 2 7 15 10 4 16 5 1 8 12 6 3 14 // merge 1

9 13 2 11 7 15 10 4 16 5 1 8 12 6 3 14 // merge 2

Explanation / Answer

13 9 11 2 7 15 10 4 16 5 1 8 12 6 3 14 // given array
9 13 11 2 7 15 10 4 16 5 1 8 12 6 3 14 // merge 1
9 13 2 11 7 15 10 4 16 5 1 8 12 6 3 14 // merge 2
9 13 2 11 7 15 10 4 16 5 1 8 12 6 3 14 // merge 3
9 13 2 11 7 15 4 10 16 5 1 8 12 6 3 14 // merge 4
9 13 2 11 7 15 4 10 5 16 1 8 12 6 3 14 // merge 5
9 13 2 11 7 15 4 10 5 16 1 8 12 6 3 14 // merge 6
9 13 2 11 7 15 4 10 5 16 1 8 6 12 3 14 // merge 7
9 13 2 11 7 15 4 10 5 16 1 8 6 12 3 14 // merge 8
2 9 11 13 7 15 4 10 5 16 1 8 6 12 3 14 // merge 9
2 9 11 13 4 7 10 15 5 16 1 8 6 12 3 14 //merge10
2 9 11 13 4 7 10 15 1 5 8 16 6 12 3 14 //merge 11
2 9 11 13 4 7 10 15 1 5 8 16 3 6 12 14 //merge 11
2 4 7 9 10 11 13 15 1 5 8 16 3 6 12 14 //merge 12
2 4 7 9 10 11 13 15 1 3 5 6 8 12 14 16 //merge 13
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 //merge 14

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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