Advanced Sorting Algorithms: Merge Sort, Quick Sort, and Heap Sort Quiz Quiz

Challenge your understanding of advanced sorting algorithms including Merge Sort, Quick Sort, and Heap Sort. This quiz explores key concepts, performance considerations, and unique properties to help solidify your knowledge of efficient data sorting techniques.

1. Merge Sort Time Complexity

   What is the average-case time complexity of Merge Sort when sorting an array of n distinct integers?

   1. O(log n)
   2. O(n)
   3. O(n^2)
   4. O(n log n)

   Explanation: Merge Sort consistently performs at O(n log n) time complexity in the average case, due to its divide-and-conquer approach that splits and merges arrays recursively. O(n^2) is typical of less efficient algorithms like Bubble Sort. O(log n) and O(n) are not accurate for Merge Sort's overall sorting performance, as the algorithm must process each element multiple times.

2. Quick Sort Pivot Choice Impact

   How does the choice of pivot affect Quick Sort’s performance, such as when sorting an already sorted list?

   1. It can cause Quick Sort to degrade to O(n^2) if the worst pivot is chosen
   2. It makes Quick Sort unstable but does not impact performance
   3. Quick Sort always runs in O(n log n), regardless of pivot selection
   4. Pivot choice does not affect Quick Sort’s performance at all

   Explanation: If Quick Sort consistently picks the smallest or largest element as a pivot on sorted or nearly sorted data, performance drops to O(n^2) due to highly unbalanced partitions. Claiming pivot choice has no effect or that Quick Sort is always O(n log n) ignores practical impact. Instability relates to element order, not time complexity, so that option is also incorrect.

3. Heap Sort Property

   Which property does Heap Sort possess that differentiates it from both Merge Sort and the most common implementations of Quick Sort?

   1. Heap Sort has O(n^2) average-case time complexity
   2. Heap Sort sorts in-place without extra memory for recursion
   3. Heap Sort cannot be used for arrays
   4. Heap Sort is always stable

   Explanation: Heap Sort is in-place and does not need additional recursion stacks or merge buffers, unlike Merge Sort which needs extra space, and basic Quick Sort implementations which may use stack space for recursion. Heap Sort is not stable by default, so option two is false. Option three is incorrect, as Heap Sort works well on arrays. Option four is incorrect, since Heap Sort is O(n log n) on average.

4. Merge Sort Stability

   Why is Merge Sort considered a stable sorting algorithm when sorting objects with duplicate keys?

   1. Because equal elements retain their original relative order after sorting
   2. Because it sorts elements by overwriting their values
   3. Because Merge Sort uses a randomized pivot
   4. Because it only compares adjacent elements

   Explanation: Merge Sort ensures that equal elements appear in the same order as they were in the input, satisfying the definition of stability. Using a randomized pivot is a characteristic of Quick Sort, not Merge Sort. Overwriting values or comparing only adjacent elements does not guarantee stability, making those distractors inaccurate.

5. Quick Sort Partitioning

   During Quick Sort's partition phase, what is the role of the partitioning index with respect to the pivot element?

   1. It is only used to find duplicate values
   2. It sorts the entire array in one pass
   3. It always places the largest element at the start
   4. It divides the array so that elements left of the index are less than the pivot, and right are greater or equal

   Explanation: The partitioning index is key to the Quick Sort process, ensuring elements to its left are less than the pivot and those to its right are greater or equal. The partitioning step does not guarantee to place the largest element first or sort the entire array in a single pass. The index is not specifically for finding duplicates, making the other options incorrect.