# MergeSort

## Algorithms and Datastructures :: 05-06-2018

These notes might change over time, some might also be incomplete. If you find any errors or misleading text, please comment about it.

Mergesort merges lists into atomic parts and then combines them back into a sorted list. Ex [5,3,10,2] → [5,3],[10,2] → [5],[3],[10],[2] → [3,5],[2,10] → [2,3,5,10]

The code for merge is

Merge(A,p,q,r) n_{1} = q - p + 1 n_{2} = r - q let L[1 ... n_{1} + 1] let R[1 ... n_{2} + 1] for i = 1 to n_{2} L[i] = A[p + i - 1] for j = 1 to n_{2} R[j] = A[q + j] L[n_{1} + 1] = ∞ R[n_{2} + 1] = ∞ i = 1 j = 1 for k = p to r if L[i] \leq R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1

That is it merges two lists into one sorted:

{1,4},{2,5} {4},{2,5} \rightarrow {1} {4},{5} \rightarrow {1,2} {5} \rightarrow {1,2,4} {} \rightarrow {1,2,4,5}

And the code for merge-sort is

Merge-Sort(A,p,r) if q < r q = ceil((p + r) / 2) Merge-Sort(A,p,q) Merge-Sort(A,q + 1,r) Merge(A,p,q,r)

Ways to calculate time complexity on recursive methods

• Recursion trees (used to guess)
• Master method (used as a shortcut)
• Substitution (Universal)

Mergesort equation $$T(n) = \begin{cases} T(1) & n = 1 \\ 2 T(n/2) + n & n > 1 \end{cases}$$

The recursion tree can be drawn for 3 levels as follows

Which seems like $O(n lg(n))$. Let's proof that by using the substitution method. So guess $c \cdot n \cdot lg(n)$. Base cases are $n = 2$ and $n = 3$ - we need to chose two to avoid relying on $n = 1$. $$T(2) = 2 \cdot 1 + 2 \leq c \cdot 2$$ and $$T(3) = 2 \cdot 3/2 + 3 \leq c \cdot 3$$ And for the induction step. Assume strongly that $T(n - 1) \leq c(n - 1)lg(n -1)$, that is for all $n_0 \leq n - 1$ and especially $n/2$. Now we get $$T(n/2) \leq (n/2) \cdot c \cdot lg(n/2) \Rightarrow \\ 2T(n/2) \leq n \cdot c \cdot lg(n/2) \Rightarrow \\ 2T(n/2) + n \leq n \cdot c \cdot lg(n / 2) + n \Rightarrow \\ T(n) \leq n \cdot c(lg(n) - lg(2)) + n \Rightarrow \\ T(n) \leq c \cdot n \cdot lg - c \cdot n + n \leq c \cdot n \cdot lg(n)$$ for $c \geq 1$, and we are done.