13.4. Complexity Analysis

Try these first

1. 1.

   Describe the key steps of the Merge Sort algorithm.

   Hint

   Think about the three important actions.

2. 2.

   What is the time complexity of Merge Sort?

   Hint

   Consider how the divide-and-conquer strategy affects the performance.

3. 3.

   What is the time complexity of Merge Sort?

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

   Hint

   Think about how the merging process contributes to the overall efficiency.

4. 4.

   True or False: Merge Sort can sort linked lists efficiently.

   • True
   • False

   Hint

   Consider how linked lists are structured.

5. 5.

   Design an algorithm that combines two sorted arrays without using an additional array.

   Hint

   Consider how to shift elements as you iterate.

6. 6.

   Explain how Merge Sort can be executed on linked lists and discuss its advantages.

   Hint

   Think about the properties of linked lists compared to arrays.