Data Structures and Algorithms
In merge sort, the two sorted runs 1, 4, 7, 9 and 2, 3, 8, 10 are merged into one by repeatedly comparing their front elements and outputting the smaller. When one run is empty, the rest of the other is output without comparisons. How many comparisons are made?
- A4
- B7
- C8
Show answer and explanation
Answer: B. 7
The comparisons are 1 vs 2, 4 vs 2, 4 vs 3, 4 vs 8, 7 vs 8, 9 vs 8 and 9 vs 10; at that point the first run is empty, so the remaining 10 is output without a comparison. That is 7 comparisons, the maximum m + n − 1 = 7 for merging runs of lengths m and n. A merge looks at each element of the sorted runs only once, so it takes O(m + n), and since merge sort repeats this over log₂ n levels, the whole sort takes O(n log n).
- A. It is not enough to compare only as many times as one run's length. The values alternate between the runs, so more comparisons are needed.
- B. Correct. Only the last value, 10, is output without a comparison, so there are 7 comparisons.
- C. The last element has nothing left to be compared with, so the count is not 8.