Test on Merge sort

Question 1: The 'Divide' step of the 'divide and conquer' paradigm, as applied by Merge Sort, involves creating sublists until each contains only one element, and these single-element sublists are then directly merged.

A. Yes

B. No

Explanation: According to the study materials, the 'Divide' step of the 'divide and conquer' paradigm involves dividing the unsorted list into 'n sublists, each containing one element'. However, the 'Conquer' step then states 'Each sublist is recursively sorted. In practice, this step involves repeatedly splitting the list in half until individual elements are reached.' This implies an intermediate recursive sorting/splitting step before the 'Combine (Merge)' phase begins.

Question 2: Merge Sort is unsuitable for sorting linked lists because it requires random access to elements.

A. Yes

B. No

Explanation: Merge Sort is particularly well-suited for sorting linked lists because it does not require random access to elements, only sequential access. Therefore, the statement that it is unsuitable because it requires random access is incorrect.

Question 3: What is the primary operational mechanism used by the `merge` function in Merge Sort to combine two sub-arrays into a single sorted array?

A. It compares the first elements of both sub-arrays, picking the smaller one, and adds it to a new result array.

B. It directly appends one sub-array to the end of the other, then performs an insertion sort on the combined array.

C. It sorts each sub-array again using a different sorting algorithm before combining them.

D. It concatenates the two sub-arrays and then sorts the entire combined array from scratch using quicksort.

Explanation: The study materials state: 'The core of the Merge Sort algorithm lies in its `merge` function. This function takes two already sorted sub-arrays and combines them into a single, larger sorted array. It does this by comparing the first elements of both sub-arrays, picking the smaller one, and adding it to the result array. This process continues until all elements from both sub-arrays have been moved to the result array. If one sub-array runs out of elements, the remaining elements of the other sub-array are simply appended to the result, as they are already sorted relative to each other.'

Question 4: According to the provided study materials, what is the primary reason for Merge Sort's O(n) space complexity?

A. The repeated division of the array into halves creates numerous sub-arrays.

B. An auxiliary array is typically required during the merge operation to store combined sorted results.

C. It is necessary to store the original unsorted data alongside the sorted results to ensure stability.

D. The recursive calls consume a significant amount of stack space for each level of division.

Explanation: The study materials state: "The space complexity of Merge Sort is O(n), where n is the number of elements in the array. This is primarily because the `merge` operation typically requires an auxiliary array of size proportional to the total number of elements being merged to store the combined sorted results." This directly supports option 1.

Question 5: The recursive nature of Merge Sort can introduce overhead due to function call stack management.

A. Yes

B. No

Explanation: The recursive nature of Merge Sort introduces overhead due to function call stack management, though this is usually negligible for typical problem sizes.