14.1.2. The Merge Operation

Try these first

1. 1.

   What does the merge operation do?

   Hint

   Think about the ordered form of both lists.

2. 2.

   What is the time complexity of the merge operation?

   Hint

   Consider the sizes of both lists.

3. 3.

   What is the overall complexity of merge sort?

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

   Hint

   Consider how it divides the input.

4. 4.

   The merge operation requires how much additional space?

   • O(1)
   • O(n)
   • O(m+n)

   Hint

   Think about how data is transferred.

5. 5.

   Given two sorted lists A = [1, 3, 5] and B = [2, 4, 6], describe how to merge them without duplicates.

   Hint

   Think about how you can ensure that duplicates are only included once.

6. 6.

   Discuss why merge sort's auxiliary space usage may be a drawback in certain applications.

   Hint

   Consider environments with tight resource constraints.