Merge Sort

Merge Sort on an input sequence $S$ with $n$ elements consists of three steps:

• Divide: if $S$ has zero or one element, return $S$. Otherwise, remove all elements from $S$ and put them in two sequences, $S_1$ and $S_2$, each containing about half of the elements of $S$. $S_1$ contains the first $\lceil \frac{n}{2}\rceil$ elements of $S$ and $S_2$ contains remaining $\lfloor \frac{n}{2}\rfloor$ items.
• Recur: recursively sort $S_1$ and $S_2$
• Conquer: merge $S_1$ and $S_2$ into a sorted sequence $S$

The base case for the recursion are subproblems of size $0$ or $1$.