Merge sort

…

Properties

• $\Theta(n)$ extra space for arrays
• $\Theta(\lg(n))$ extra space for linked lists
• $\Theta(n\cdot \lg(n))$ time
• Stable
• Not adaptive
• Does not require random access to data