Mergesort makes two recursive calls. Which statement is true after these two…
2014
Mergesort makes two recursive calls. Which statement is true after these two recursive calls finish, but before the merge step ?
- A.
The array elements form a heap.
- B.
Elements in each half of the array are sorted amongst themselves.
- C.
Elements in the first half of the array are less than or equal to elements in second half of the array.
- D.
All of the above
Attempted by 593 students.
Show answer & explanation
Correct answer: B
Answer: Elements in each half of the array are sorted amongst themselves.
Explanation: After the two recursive mergesort calls complete on the left and right portions, each portion is individually sorted. The merge step that follows is responsible for combining these two sorted halves into a single sorted array.
Key consequence: The left half is sorted and the right half is sorted.
Why other statements are false: The array does not form a heap because mergesort does not perform heap operations; heapsort builds a heap.
Counterexample to the claim that all elements in the first half are <= all elements in the second half: left = [3, 4], right = [1, 2] — each half is sorted but elements across halves are not ordered.
Role of merge: The merge step takes advantage of the two sorted halves to produce the final sorted array in linear time.