14.1.7. Limitations of Merge Sort

Try these first

1. 1.

   What is the primary function of merge sort?

   Hint

   Think about how it handles large datasets.

2. 2.

   What is a limitation of merge sort?

   Hint

   Consider how the elements are combined.

3. 3.

   What is the time complexity of merge sort?

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

   Hint

   Think about how many times the input is halved.

4. 4.

   True or False: Merge sort requires additional memory.

   • True
   • False

   Hint

   Consider how the merging process works.

5. 5.

   Given an array with 1 billion integers, discuss how merge sort would perform and compare it with quicksort in terms of memory usage.

   Hint

   Consider the balance between speed and memory efficiency.

6. 6.

   Propose an algorithm to optimize the merging process in merge sort to reduce memory utilization.

   Hint

   Think about how to sort without needing extra space.