13.1.5. Formalizing Merge Sort Algorithm

Try these first

1. 1.

   What is the main advantage of Merge Sort over other sorting algorithms?

   Hint

   Think about time complexity.

2. 2.

   What does the merging step in Merge Sort involve?

   Hint

   How do you compare two lists?

3. 3.

   What is the time complexity of Merge Sort?

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

   Hint

   Think about how many times the input array is divided.

4. 4.

   True or False: Merge Sort is an in-place sorting algorithm.

   • True
   • False

   Hint

   Consider whether extra space is needed.

5. 5.

   Consider an array of integers: [34, 7, 23, 32, 5, 62]. Explain how Merge Sort would process this array step by step.

   Hint

   Focus on the divide and then how merging happens.

6. 6.

   Analyze the impact of Merge Sort on a large dataset (over a million entries) compared to Bubble Sort. What conclusions can you draw from their performances?

   Hint

   Think about their time complexities.