# Merge Sort

## Algorithm

proc merge-sort(A, p, r)
if p < r then
q = floor((p + r)/2)
merge-sort(A, p, q)
merge-sort(A, q+1, r)
merge(A, (p,q), (q+1,r))

## Merge comparisons

Assuming we have equal partitions with length $m$, the best is (consecutive partitions) is $m$ and the worst (interleaved partitions) is $2m-1$.

Given different sized partitions $m\le l$ the worst case comparisons is $m+l-1$. When $m$ is significantly less than $l$ you can use binary search to improve performance.

## Merge sort comparisons

We will only analyze the worst case. The recurrence is:

$T\left(n\right)=\{\begin{array}{cc}0& ifn=0\\ 2T\left(\frac{n}{2}\right)+(n-1)& \text{otherwise}\end{array}$

The closed-form is $T\left(n\right)=nlgn-n+1$.