Which of the following is a common use case for Merge Sort?
Sorting a small array with less than 10 elements
Sorting a nearly sorted array
Sorting a linked list
Finding the smallest element in an array
What is the worst-case time complexity of Heap Sort?
O(n)
O(n^2)
O(n log n)
O(log n)
What is the worst-case time complexity of Quick Sort and when does it occur?
O(n^2), when the input array is already sorted or reverse sorted
O(n log n), when the pivot is always the median element
O(n^2), when the pivot is always the median element
O(n log n), when the input array is sorted or reverse sorted
Which of the following is a key advantage of Merge Sort?
In-place sorting
Stable sorting
Best-case time complexity of O(n)
Constant space complexity
What is the space complexity of Bucket Sort in the average case, assuming a suitable hash function and uniform data distribution?
O(1)
What is the primary motivation behind using randomized Quick Sort?
To simplify the implementation of the partitioning step compared to deterministic pivot selection methods.
To make the algorithm's running time completely independent of the input data.
To make the sorting process more unpredictable and challenging for analysis.
To provide a probabilistic guarantee of achieving the average-case time complexity, even for potentially adversarial input sequences.
What is a key characteristic of in-place partitioning within the context of Quick Sort?
The partitioning step always selects the first element of the subarray as the pivot.
The algorithm sorts the array by recursively dividing it into smaller subarrays and then merging them back together.
The partitioning process is performed entirely within the original array, without requiring the allocation of substantial additional memory proportional to the input size.
In-place partitioning is only applicable when the input array is already sorted in reverse order.
How does sorting contribute to efficient data organization in databases and file systems?
Sorting has no direct impact on data organization; it's solely used for arranging data in a specific order.
Sorting reduces the overall storage space required for the data.
Sorting makes data retrieval faster by enabling the use of efficient search algorithms like binary search.
Sorting enhances data security by making it more difficult for unauthorized users to access sensitive information.
In the context of Heap Sort, what is the process called where we ensure that a subtree maintains the heap property?
Heapify
Sift-down
Sift-up
Heap-balance
Counting sort is often used as a subroutine in which other sorting algorithm?
Merge Sort
Heap Sort
Radix Sort
Quick Sort