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

Starter code for this chapter.