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)$ 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)$ for sorted subarrays, and why this results in $O(n)$ for already sorted starting sequences.

Starter code for this chapter.