In which case does Merge Sort outperform Quick Sort?
a) When sorting small datasets
b) When the dataset is already sorted
c) When dealing with large datasets and worst-case scenarios
d) When the dataset contains duplicates
Answer:
c) When dealing with large datasets and worst-case scenarios
Explanation:
Merge Sort outperforms Quick Sort in worst-case scenarios, where Quick Sort has a time complexity of O(n^2). Merge Sort guarantees a time complexity of O(n log n) in both the worst and average cases, making it more predictable for large datasets.
However, Merge Sort requires additional memory for the merge step, whereas Quick Sort works in-place. Despite this, Merge Sort is stable, which means it preserves the relative order of equal elements.
Merge Sort is commonly used in applications where stability and predictable performance are important, such as external sorting with large datasets.
Reference:
DSA (Data Structures and Algorithms) MCQ Questions and Answers