14.1.3. Time Complexity of Merge Sort

Try these first

1. 1.

   What is the time complexity of the merge operation?

   Hint

   Think about how we process each element in both lists.

2. 2.

   What does T(n) represent in the context of merge sort?

   Hint

   Recall what we mentioned about T(n) and its relation to recursion.

3. 3.

   What is the time complexity of merge sort?

   • O(n^2)
   • O(n log n)
   • O(n)

   Hint

   Think about the efficiency compared to simpler sorting methods.

4. 4.

   The merge operation takes linear time. True or False?

   • True
   • False

   Hint

   Recall how each element from the lists is compared and moved.

5. 5.

   Design a hybrid sorting algorithm that integrates merge sort with quicksort principles. How would you handle the merging phase?

   Hint

   Consider the size of the array before selecting the sorting method.

6. 6.

   Consider implementing merge sort without using additional arrays for merging. Discuss alternative methods and their potential drawbacks.

   Hint

   Think about how in-place sorting compares to the standard merge method.