Why is Merge Sort often preferred over simpler algorithms like Bubble Sort for large datasets?
Merge Sort has a lower space complexity than Bubble Sort.
Merge Sort's time complexity scales better with increasing data size.
Merge Sort's recursive approach is easier to implement.
Merge Sort is an in-place sorting algorithm, while Bubble Sort is not.
What is a key characteristic of in-place partitioning within the context of Quick Sort?
The partitioning process is performed entirely within the original array, without requiring the allocation of substantial additional memory proportional to the input size.
The algorithm sorts the array by recursively dividing it into smaller subarrays and then merging them back together.
The partitioning step always selects the first element of the subarray as the pivot.
In-place partitioning is only applicable when the input array is already sorted in reverse order.
Bucket Sort achieves its efficiency by:
Using a priority queue to maintain sorted order during insertion
Distributing elements into buckets based on their range
Exploiting the relative order of elements within the input
Recursively dividing the input into smaller subproblems
What is the space complexity of Merge Sort?
O(1)
O(n)
O(log n)
O(n log n)
What is the space complexity of Bucket Sort in the average case, assuming a suitable hash function and uniform data distribution?
What is the worst-case time complexity of Quick Sort and when does it occur?
O(n^2), when the pivot is always the median element
O(n log n), when the input array is sorted or reverse sorted
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
Is Merge Sort an in-place sorting algorithm?
Yes
No
Which of the following is a common use case for Merge Sort?
Sorting a nearly sorted array
Finding the smallest element in an array
Sorting a linked list
Sorting a small array with less than 10 elements
Is Heap Sort a stable sorting algorithm?
What is the significance of lexicographic sorting in string processing?
It sorts strings based on their lengths, from shortest to longest or vice versa.
It sorts strings in alphabetical order, considering the order of characters defined by the character encoding (e.g., ASCII or Unicode).
It sorts strings based on the number of vowels they contain.
It sorts strings based on their hash values, making it very efficient for comparing large strings.