Merge Sort

After reading this chapter and engaging in the embedded activities and reflections, you should be able to:

  • Explain and trace the operations of MergeSort on a particular data sequence.
  • Implement MergeSort efficiently (allowing O(n)\Omicron(n) auxiliary space).
  • Analyze the best- and worst-case space and time efficiency of merge phase and MergeSort overall.
  • Determine how to optimize the merge phase to be O(1)\Omicron(1) for sorted subarrays and why this results in O(n)\Omicron(n) for already sorted starting sequences.

Starter code for this chapter.

Solution code

Solution code for this chapter.