29.3 Mergesort

We've covered mergesort in the past, but as a reminder, the algorithm is as follows:

1. Split the items into half.

2. Mergesort each half.

3. Merge the two sorted halves to form the final result.

You can see a demo of the algorithm here.

Mergesort has a runtime of $\Theta(N \log N)$-- we will not reanalyze the algorithm here but you may refer to this link if you'd like to remind yourself.

The auxiliary array used during the merge step requires $\Theta(N)$ extra space. Note that in-place mergesort is possible; however it is very complex and the runtime suffers by a significant constant factor, so we will not cover it here.