14.1.1. Introduction to Merge Sort

Try these first

1. 1.

   What is the runtime complexity of Merge Sort?

   Hint

   Think about how dividing the list and merging affects performance.

2. 2.

   Describe the main operation performed in Merge Sort.

   Hint

   Consider what you do to combine the lists.

3. 3.

   What is the time complexity of Merge Sort?

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

   Hint

   Think about how the algorithm divides the input size.

4. 4.

   True or False: Merge Sort can sort data without requiring additional memory.

   • True
   • False

   Hint

   Consider how elements need to be temporarily stored during the merge.

5. 5.

   Given two sorted lists A = [5, 10, 20] and B = [2, 5, 15], how would you merge them while accounting for duplicates?

   Hint

   Consider using two pointers to help you move through each list efficiently.

6. 6.

   Discuss a method to implement Merge Sort iteratively without recursion.

   Hint

   Think about how you could maintain the state of sorted sublists.