Why is Merge Sort often preferred over simpler algorithms like Bubble Sort for large datasets?
Merge Sort's recursive approach is easier to implement.
Merge Sort is an in-place sorting algorithm, while Bubble Sort is not.
Merge Sort has a lower space complexity than Bubble Sort.
Merge Sort's time complexity scales better with increasing data size.
What is the primary advantage of using counting sort over comparison-based sorting algorithms like merge sort or quick sort?
Counting sort is a stable sorting algorithm by default.
Counting sort works efficiently even for large datasets with a wide range of values.
Counting sort can achieve a time complexity better than O(n log n) in certain scenarios.
Counting sort is an in-place sorting algorithm.
What is the primary motivation behind using randomized Quick Sort?
To make the sorting process more unpredictable and challenging for analysis.
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 provide a probabilistic guarantee of achieving the average-case time complexity, even for potentially adversarial input sequences.
Why is Quick Sort often preferred over Merge Sort in practice, despite having the same average-case time complexity?
Quick Sort has a lower constant factor in its time complexity, making it faster for smaller datasets
Quick Sort is easier to parallelize and implement on multi-core processors
Quick Sort is an in-place sorting algorithm, while Merge Sort requires additional space for merging
Quick Sort is more memory-efficient due to its recursive nature
Which of the following is a key advantage of Merge Sort?
Best-case time complexity of O(n)
Stable sorting
In-place sorting
Constant space complexity
In counting sort, what does the count array store?
The frequency of each distinct element in the input array.
The indices of elements in the input array.
The sorted elements of the input array.
The cumulative sum of frequencies of elements less than or equal to each element in the input array.
What is the primary advantage of using a binary heap in Heap Sort?
Constant time insertion of elements
Maintaining a sorted order during element extraction
Low memory overhead compared to other heap structures
Efficient searching of elements
What is the space complexity of Merge Sort?
O(1)
O(n log n)
O(n)
O(log n)
What is the worst-case time complexity of Heap Sort?
O(n^2)
Radix Sort utilizes which of the following properties of the input data to achieve its efficiency?
Order statistics of the data
Pre-sortedness of the data
Frequency of occurrence of data elements
Distribution of the data values within a range