# 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](https://docs.google.com/presentation/d/1h-gS13kKWSKd_5gt2FPXLYigFY4jf5rBkNFl3qZzRRw/edit#slide=id.g463de7561_042). 

Mergesort has a runtime of $$\Theta(N \log N)$$-- we will not reanalyze the algorithm here but you may refer to this [link](https://docs.google.com/presentation/u/1/d/1_LhI5V5JlcRHYU55_SF7ZHxPemBr9OVlNzj7ScYdg64/edit#slide=id.g84271d11b_2_77) 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.