Apply the merge sort to each of the following lists. Draw the splitting and merg

Question

Apply the merge sort to each of the following lists. Draw the splitting and merging trees for each application of the procedure.


?1, 7, 4, 11, 5, ?8, 15, ?3, ?2, 6, 10, 3

Explanation / Answer

The following uses | to indicate subdivisions, to show the range of a merge. A description of each step is in brackets. Specific comparisons are noted in parentheses. 11, 7, 19, 18, 1000, -9, 0, 2 [initial array] 11, 7, 19, 18 | 1000, -9, 0, 2 [divided once] 11, 7 | 19, 18 | 1000, -9, 0, 2 [first half divided again] 11 | 7 | 19, 18 | 1000, -9, 0, 2 [divided again] < 11 | 7 >| 19, 18 | 1000, -9, 0, 2 [begin merge] 7 < 11 >| 19, 18 | 1000, -9, 0, 2 [continue merge] (compared: 11 to 7) 7, 11 | 19, 18 | 1000, -9, 0, 2 [merge complete] 7, 11 | 19 | 18 | 1000, -9, 0, 2 [next part divided] 7, 11 |< 19 | 18 >| 1000, -9, 0, 2 [begin merge] 7, 11 | 18 < 19 >| 1000, -9, 0, 2 [continue merge] (19 to 18) 7, 11 | 18, 19 | 1000, -9, 0, 2 [merge complete] < 7, 11 | 18, 19 >| 1000, -9, 0, 2 [begin next merge] 7 < 11 | 18, 19 >| 1000, -9, 0, 2 [continue merge] (7 to 18) 7 , 11 < 18, 19 >| 1000, -9, 0, 2 [continue merge] (11 to 18) 7 , 11 , 18 < 19 >| 1000, -9, 0, 2 [continue merge] 7, 11, 18, 19 | 1000, -9, 0, 2 [merged first half] 7, 11, 18, 19 | 1000, -9 | 0, 2 [subdividing second half] 7, 11, 18, 19 | 1000 | -9 | 0, 2 [subdividing again] 7, 11, 18, 19 | < 1000 | -9 >| 0, 2 [begin merge] 7, 11, 18, 19 | -9 < 1000 >| 0, 2 [continue merge] (1000 to -9) 7, 11, 18, 19 | -9, 1000 | 0, 2 [merge complete] 7, 11, 18, 19 | -9, 1000 | 0 | 2 [subdividing] 7, 11, 18, 19 | -9, 1000 | < 0 | 2 > [begin merge] 7, 11, 18, 19 | -9, 1000 | 0 < 2 > [continue merge] (0 to 2) 7, 11, 18, 19 | -9, 1000 | 0, 2 [merge complete] 7, 11, 18, 19 | < -9, 1000 | 0, 2 > [begin merge] 7, 11, 18, 19 | -9 < 1000 | 0, 2 > [continue merge] (-9 to 0) 7, 11, 18, 19 | -9 , 0 < 1000 | 2 > [continue merge] (1000 to 0) 7, 11, 18, 19 | -9 , 0, 2 < 1000 > [continue merge] (1000 to 2) 7, 11, 18, 19 | -9 , 0, 2, 1000 [merge complete] < 7, 11, 18, 19 | -9 , 0, 2, 1000 > [begin merge] -9 < 7, 11, 18, 19 | 0, 2, 1000 > [continue merge] (7 to -9) -9, 0 < 7, 11, 18, 19 | 2, 1000 > [continue merge] (7 to 0) -9, 0 , 2 < 7, 11, 18, 19 | 1000 > [continue merge] (7 to 2) -9, 0, 2, 7 < 11, 18, 19 | 1000 > [continue merge] (7 to 1000) -9, 0, 2, 7, 11 < 18, 19 | 1000 > [continue merge] (11 to 1000) -9, 0, 2, 7, 11, 18 < 19 | 1000 > [continue merge] (18 to 1000) -9, 0, 2, 7, 11, 18, 19 < 1000 > [continue merge] (19 to 1000) -9, 0, 2, 7, 11, 18, 19, 1000 [merge and sort complete]

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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