13.4.1. Analysis of Merge Sort Complexity

Try these first

1. 1.

   What does merge sort do?

   Hint

   Think about how it handles subarrays.

2. 2.

   Can merge sort handle arrays of odd size?

   Hint

   What happens when you divide an odd number?

3. 3.

   What is the time complexity of merge sort?

   • O(n²)
   • O(n log n)
   • O(n)

   Hint

   Consider how the array is divided and merged.

4. 4.

   True or False: Merge sort can sort an array of any size effectively.

   • True
   • False

   Hint

   What happens when sizes are not examples of powers of two?

5. 5.

   Given an array of numbers, implement the merge sort algorithm in code. Analyze the time taken for sorting an array of large size.

   Hint

   Pay attention to the merging step and ensure the recursion captures both halves correctly.

6. 6.

   Compare and analyze the performance of merge sort and insertion sort on an array of 1000 random integers. Present your findings.

   Hint

   Consider the arrangement of elements as they are sorted.