Merge Sort

Overview

Mergesort recursively calls itself on the halves of an array, bottoming out at an array with $\le 1$ element. It then calls a merging algorithm on the two sorted halves.

Property	Value
Best Case	$\mathrm{\Omega }(n\lg n)$
Worst Case	$O(n\lg n)$
Avg. Case	$O(n\lg n)$
Aux. Memory	$O(n)$
Stable	-
Adaptive	-
Visualization