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 Merge Sort on a particular data sequence.
• Implement Merge Sort efficiently (allowing $\Omicron(n)$ auxiliary space).
• Analyze the best- and worst-case space and time efficiency of merge phase and Merge Sort 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.