What is the primary mechanism behind Merge Sort's efficiency?
Using a hash table to store and retrieve sorted elements
Iterative comparison of adjacent elements
Recursive division of the input array into smaller subarrays
Building a binary search tree from the input data
What is a potential limitation of Heap Sort compared to some other efficient sorting algorithms?
It requires the entire dataset to be in memory.
It is not well-suited for sorting linked lists.
It is less efficient when the input data is already nearly sorted.
Its average-case time complexity is worse than some other algorithms.
Bucket Sort can be considered a stable sorting algorithm under which condition?
The input data is already sorted.
The underlying sorting algorithm used within each bucket is stable.
The number of buckets is equal to the number of elements.
Bucket Sort is inherently stable regardless of the input or implementation.
How does the time complexity of Radix Sort compare to comparison-based sorting algorithms like Merge Sort and Quick Sort for integers with a wide range?
Radix Sort can be faster under certain conditions
Radix Sort is consistently faster
Radix Sort has the same time complexity
Radix Sort is always slower
What is the space complexity of Bucket Sort in the average case, assuming a suitable hash function and uniform data distribution?
O(n log n)
O(n)
O(log n)
O(1)
How does tail recursion optimization benefit the implementation of Quick Sort?
It improves the average-case performance of the algorithm but does not affect the worst case
It simplifies the implementation of the partitioning scheme
It prevents stack overflow errors by converting recursion into iteration
It reduces the time complexity of the algorithm from O(n^2) to O(n log n)
Which of the following statements accurately describes the stability of Quick Sort?
The stability of Quick Sort depends on the input data
Quick Sort is inherently stable
Quick Sort can be easily modified to be stable
Quick Sort is inherently unstable
In the context of Heap Sort, what is the process called where we ensure that a subtree maintains the heap property?
Sift-down
Sift-up
Heapify
Heap-balance
What is the worst-case time complexity of Quick Sort and when does it occur?
O(n log n), when the input array is sorted or reverse sorted
O(n^2), when the pivot is always the median element
O(n log n), when the pivot is always the median element
O(n^2), when the input array is already sorted or reverse sorted
What is the worst-case time complexity of Heap Sort?
O(n^2)