14.1. Merge Sort: Analysis

Try these first

1. 1.

   What is the time complexity of the merge operation in Merge Sort?

   Hint

   Think about how you process each element while merging.

2. 2.

   Define Merge Sort in one sentence.

   Hint

   Remember that it breaks the list down into smaller pieces.

3. 3.

   What is the overall time complexity of Merge Sort?

   • O(n)
   • O(n log n)
   • O(n²)

   Hint

   Recall how the algorithm processes data.

4. 4.

   True or False: Merge Sort can be performed in-place, without additional storage.

   • True
   • False

   Hint

   Consider the merging step and its requirements.

5. 5.

   Design an iterative version of Merge Sort and explain the changes required compared to the recursive version.

   Hint

   Think about converting the recursive calls into loops.

6. 6.

   Consider a list with duplicate elements. How would the merge function be adjusted to avoid duplicates in the merged output?

   Hint

   Think how you'd handle equality in the merge step.