Merge Sort

Overview

Merge sort is one of the three solid $\Theta (n\log {n})$ sort algorithms. (The other two are heap sort and (randomized) quick sort.)

Brief Description

Merge sort is the sort analogue of binary search - we sort by continually splitting the array of data in half, until we reach the trivial case of an array with a single piece of data in it. Each recursive instance of merge sort then has a single piece of data, and these functions begin to merge their sorted results together.

Implementation

Merge Sort/Pseudocode

Merge Sort/Python

Merge Sort/Java

Merge Sort/Go

Algorithm Analysis

Because the continual splitting in half is O(log n) per step, for O(n log n) overall, and because the merge operation is linear, O(n), we can use the Master Theorem to prove a stronger result than O(n log n). We can show:

$T(n)=\Theta \left(n\log {n}\right)$

See Algorithm Analysis/Merge Sort for the Master Theorem analysis of merge sort.