13.1.2. Combining Sorted Lists

Try these first

1. 1.

   What is the purpose of merging in the merge sort algorithm?

   Hint

   Think about how you would sort two stacks of cards.

2. 2.

   State the base case for the merge sort algorithm.

   Hint

   Consider when no sorting is needed.

3. 3.

   What is the time complexity of merge sort?

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

   Hint

   Think about how many splits and merges occur.

4. 4.

   True or False: Merge sort is unstable, meaning it does not preserve the input order of equal elements.

   • True
   • False

   Hint

   Consider examples with duplicate elements.

5. 5.

   Given two sorted arrays A = [1, 3, 5] and B = [2, 4, 6], write a function to merge them without using additional arrays.

   Hint

   Think about how to use indexes of each array to insert elements directly.

6. 6.

   Create a visual representation of the merge sort algorithm applied to the array [12, 11, 13, 5, 6, 7]. Describe the merge steps as you go.

   Hint

   Document each comparison during the merging process to illustrate the order.