14.1.4. Improvement Over Other Sorting Algorithms

Try these first

1. 1.

   What is the time complexity of merge sort?

   Hint

   Recall the significant term in time complexity discussion.

2. 2.

   What is the purpose of the merge operation in merge sort?

   Hint

   Think of how sorted lists are merged during the process.

3. 3.

   What is the time complexity of merge sort?

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

   Hint

   Remember the efficiency discussed in relation to input size.

4. 4.

   Does merge sort require extra space during the merging process?

   • True
   • False

   Hint

   Think about the requirements of the merge operation.

5. 5.

   Given two sorted arrays A = [1, 3, 5] and B = [2, 4, 6], write pseudocode for the merge operation.

   Hint

   Focus on the comparison and how to move through both lists.

6. 6.

   Analyze the trade-offs of using merge sort over quicksort for sorting large datasets in terms of performance and memory utilization.

   Hint

   Think about time complexity versus the need for additional memory.