Merge Sort

Computer Science Master

Question 1. What is the primary strategy used by Merge Sort to sort a list?

□ A. Divide the list into sub-lists, sort individually, and then merge

□ B. Iteratively compare adjacent elements and swap them

□ C. Select a pivot element and partition the list around it

□ D. Build a heap and extract the largest element repeatedly

Question 2. What is the worst-case time complexity of Merge Sort?

□ A. O(n²) □ B. O(n log n) □ C. O(n) □ D. O(log n)

Question 3. Which of the following is a disadvantage of Merge Sort?

□ A. It is unstable and can change the order of equal elements

□ B. It uses extra storage proportional to the input list size

□ C. It has poor performance on large lists

□ D. It is an in-place sorting algorithm

Question 4. In the Merge Sort algorithm, the merging of sub-lists involves:

□ A. Concatenating sub-lists without comparing elements

□ B. Comparing elements and combining sub-lists in sorted order

□ C. Swapping elements randomly

□ D. Reversing the sub-lists before combining

Question 5. Why might Merge Sort not be efficient for very small lists?

□ A. Because it requires too much extra storage

□ B. Because it uses recursion and has extra setup overhead

□ C. Because it only works on large lists

□ D. Because it is an unstable sort

Question 6. Fill in the blank(s)

Merge Sort follows the ___________________________ approach to sorting.

Question 7. Fill in the blank(s)

The time complexity of Merge Sort is _______________.

Question 8. Fill in the blank(s)

Merge Sort splits the unsorted list into smaller sub-lists until each sub-list has ________________.

Question 9. Fill in the blank(s)

The space complexity of Merge Sort is ______, which means it requires extra storage.

Question 10. Fill in the blank(s)

Merge Sort guarantees a _________ sort, preserving the order of equal elements.

Question 11. What does it mean that Merge Sort is a 'stable' sorting algorithm?

Question 12. Explain why Merge Sort requires extra storage space.

Question 13. What key operation does the 'merge' function perform in Merge Sort?

Question 14. Describe the base case in the recursive Merge Sort function.

Question 15. Why is Merge Sort generally preferred over simple sorting methods like Bubble Sort for large datasets?

Question 16. Describe the step-by-step process of how Merge Sort sorts an unsorted list.

Question 17. Explain the trade-offs between Merge Sort's performance advantages and its use of extra memory.

Question 18. How does the recursive nature of Merge Sort affect its implementation and understanding, especially for beginner programmers?

Merge Sort

Answer Sheet

Question 1. What is the primary strategy used by Merge Sort to sort a list?

□ A. Divide the list into sub-lists, sort individually, and then merge

B. Iteratively compare adjacent elements and swap them

C. Select a pivot element and partition the list around it

D. Build a heap and extract the largest element repeatedly

Question 2. What is the worst-case time complexity of Merge Sort?

A. O(n²) □ B. O(n log n) C. O(n) D. O(log n)

Question 3. Which of the following is a disadvantage of Merge Sort?

A. It is unstable and can change the order of equal elements

□ B. It uses extra storage proportional to the input list size

C. It has poor performance on large lists

D. It is an in-place sorting algorithm

Question 4. In the Merge Sort algorithm, the merging of sub-lists involves:

A. Concatenating sub-lists without comparing elements

□ B. Comparing elements and combining sub-lists in sorted order

C. Swapping elements randomly

D. Reversing the sub-lists before combining

Question 5. Why might Merge Sort not be efficient for very small lists?

A. Because it requires too much extra storage

□ B. Because it uses recursion and has extra setup overhead

C. Because it only works on large lists

D. Because it is an unstable sort

Question 6. Fill in the blank(s)

Merge Sort follows the [[divide and conquer]] approach to sorting.

Question 7. Fill in the blank(s)

The time complexity of Merge Sort is [[O(n log n)]].

Question 8. Fill in the blank(s)

Merge Sort splits the unsorted list into smaller sub-lists until each sub-list has [[one element]].

Question 9. Fill in the blank(s)

The space complexity of Merge Sort is [[O(n)]], which means it requires extra storage.

Question 10. Fill in the blank(s)

Merge Sort guarantees a [[stable]] sort, preserving the order of equal elements.

Question 11. What does it mean that Merge Sort is a 'stable' sorting algorithm?

It means that the order of equal elements is preserved after sorting.

Question 12. Explain why Merge Sort requires extra storage space.

Because it is not an in-place algorithm, it creates new lists during the merge step, requiring additional memory proportional to the input list size.

Question 13. What key operation does the 'merge' function perform in Merge Sort?

It compares elements of two sorted sub-lists and merges them into a single sorted list.

Question 14. Describe the base case in the recursive Merge Sort function.

When the list has one or zero elements, it is already sorted and returned as is.

Question 15. Why is Merge Sort generally preferred over simple sorting methods like Bubble Sort for large datasets?

Because Merge Sort has a better time complexity (O(n log n)) and performs more efficiently on large datasets compared to O(n²) algorithms like Bubble Sort.

Question 16. Describe the step-by-step process of how Merge Sort sorts an unsorted list.

Question 17. Explain the trade-offs between Merge Sort's performance advantages and its use of extra memory.

Question 18. How does the recursive nature of Merge Sort affect its implementation and understanding, especially for beginner programmers?