If one uses a straight two-way merge sort algorithm to sort the following…
1999
If one uses a straight two-way merge sort algorithm to sort the following elements in ascending order:
20, 47, 15, 8, 9, 4, 40, 30, 12, 17
then the order of these elements after the second pass of the algorithm is:
- A.
8, 9, 15, 20, 47, 4, 12, 17, 30, 40
- B.
8, 15, 20, 47, 4, 9, 30, 40, 12, 17
- C.
15, 20, 47, 4, 8, 9, 12, 30, 40, 17
- D.
4, 8, 9, 15, 20, 47, 12, 17, 30, 40
Attempted by 36 students.
Show answer & explanation
Correct answer: B
In straight two-way merge sort, pass 1 merges adjacent runs of length 1 into sorted runs of length 2.
Initial list:
20, 47, 15, 8, 9, 4, 40, 30, 12, 17
After pass 1:
20, 47 | 8, 15 | 4, 9 | 30, 40 | 12, 17
In pass 2, adjacent sorted runs of length 2 are merged:
20, 47 and 8, 15 -> 8, 15, 20, 47
4, 9 and 30, 40 -> 4, 9, 30, 40
12, 17 remains as the leftover sorted run.
So after the second pass, the order is:
8, 15, 20, 47, 4, 9, 30, 40, 12, 17.