13.1.3. Example of Merging Sorted Lists

Try these first

1. 1.

   What is merge sort?

   Hint

   Think about the concept of splitting and merging.

2. 2.

   Describe the base case for merge sort.

   Hint

   Consider how recursion stops.

3. 3.

   What is the time complexity of merge sort?

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

   Hint

   Think about how many times we divide the data.

4. 4.

   True or False: Merge sort is faster than insertion sort for any given input size.

   • True
   • False

   Hint

   Consider their performance characteristics.

5. 5.

   Given an array [20, 5, 23, 12, 1, 19, 3], implement merge sort and show step-by-step sorting.

   Hint

   Keep tracking the midpoints during splits.

6. 6.

   Compare merge sort and quicksort for sorting a large dataset with duplicates. Which might perform better and why?

   Hint

   Consider how the presence of duplicates affects partitions in quicksort.