> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/29.-basic-sorts/29.3-mergesort.md).

# 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.