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

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.Last modified 11mo ago