# Merge Sort

Many problems require sorting a collection of items by their keys, which are assumed to be comparable. Simple algorithums such as bubble sort and insertion sort can do this in $O(n^2)$ time, however using a divide and conquer approach, merge sort acheives $O(n \lg n)$.

Other than runtime, their are two additional characteristics we may be intrested in when comparing sorting algorithums
- __in-place__: Only $O(1)$ extra space is required to sort the array
- __stable__: For every $i$, $j$ where $i < j$ and $A[i].key = A[j].key$, $A[i]$ is guarenteed to proceed $A[j]$, 
(the ordering of equal keys remains the same).

## Algorithum

Merge sort works by recursivly splitting the array into two, until we reach arrays of size 1, which by definition are sorted.

```
Algorithum mergeSort(A, i, j)
    mid <- floor((i + j) / 2)
    mergeSort(A, i, mid)
    mergeSort(A, mid+1, j)
    merge(A, i, mid, j)
```

Merging two sorted arrays is simple. Create a scratch array $B$, then look at the first element in each of the two halves. Copy the smallest element and repeat until all elements have been copyed. Finnaly copy array $B$ back into array $A$.

```
Algorithum merge(A, i, mid, j)
    initialize array B with length j - i + 1
    k <- i
    l <- mid + 1
    m <- 0
    
    while k <= mid and l <= j do
        if A[k].key <= A[l].key then
            B[m] <- A[l].key
            k <- k + 1
        else
            B[m] <- A[l]
            l <- l + 1
        m <- m + 1
        
    while k <= mid do
        B[m] <- A[l]
        k <- k + 1
        m <- m + 1
       
    while l <= j do
        B[m] <- A[l]
        l <- l + 1
        m <- m + 1
        
    for m = 0 to j - i do
        A[m + i] <- B[m]
```

Clearly mergo sort is not _in-place_ since it uses an auxillary array $B$, however it is _stable_ since we always merge $A$ first if the keys are equal, and since all elements of $A$ came before $B$ `mergeSort` will never swap equal keys.

## Runtime

The runtime of `mergeSort` is simple, some constant amount of work for the mid point, then the sum of the three function calls.

$$
T_{mergeSort} = \begin{cases}
    O(1) & n \leq 1 \\
    O(1) + T_{mergeSort}(\lfloor{\frac{n}{2}}\rfloor) + T_{mergeSort}(\lceil{\frac{n}{2}}\rceil) + T_{merge}(n) & n \geq 2 \\
\end{cases}
$$

The worst case runtime of `merge` is $O(n)$ since their are no nested loops and each loop runs at most $n$ times. The last loop always runs $n$ times thus it is also $\Omega(n)$, thus `merge` us $\Theta(n)$.

Lets assume $n = 2^k$ for some integer $k$, thus we dont need to consider the ceil and floor's, now to solve the rest of the recurence we can expand and collect terms:

$$
\begin{align}
T_{mergeSort}(n) &= 2 T_{mergeSort}\left(\frac{n}{2}\right) + \Theta(n) \\
                 &= 2 \left(2 T_{mergeSort}\left(\frac{n}{2^2}\right) + \Theta\left(\frac{n}{2}\right)\right) + \Theta(n) \\
                 &= 4 T_{mergeSort}\left(\frac{n}{2^2}\right) + 2 \Theta\left(\frac{n}{2}\right) + \Theta(n) \\
                 &= 4 \left( 2 T_{mergeSort}\left(\frac{n}{2^3}\right) + \Theta\left(\frac{n}{2^2}\right) \right) + 2 \Theta\left(\frac{n}{2}\right) + \Theta(n) \\
                 &=  8 T_{mergeSort}\left(\frac{n}{2^3}\right) + 4 \Theta\left(\frac{n}{2^2}\right) + 2 \Theta\left(\frac{n}{2}\right) + \Theta(n) \\
                 &\vdots \\
                 &= 2^k T_{mergeSort}\left(\frac{n}{2^k}\right) + \sum_{i=0}^{k-1}{2^i \Theta{\left(\frac{n}{2^i}\right)}} \\
                 &= n T_{mergeSort}\left(1\right) + \sum_{i=0}^{k-1}{2^i \Theta{\left(\frac{n}{2^i}\right)}} \\
                 &= n \Theta(1) + \sum_{i=0}^{k-1}{2^i \Theta{\left(\frac{n}{2^i}\right)}} \\
                 &= \Theta(n) + \sum_{i=0}^{\lg n -1}{2^i \Theta{\left(\frac{n}{2^i}\right)}} \\
                 &= \Theta(n) + \Theta(n \lg n) \\
                 &= \Theta(n \lg n) \\
\end{align}
$$

To complete this proof we would use induction to fill in the "gap" when unwinding the recurance. Also, to show this works for any $n$ we use induction to show $T(n) \leq T(n+1)$ then using the facts that $n \leq 2^k < 2n$ for some $k$ and $\frac{n}{2} \leq 2^{k'} < n$ for some $k'$ we get 

$$
T(n) \leq T(2^k) = O(2^k \lg 2^k) = O(2n \lg 2n) = O(n \lg n)
$$

and

$$
T(n) = \Omega(2^{k'} \lg 2^{k'}) = \Omega\left(\frac{n}{2} \lg \frac{n}{2}\right) = \Omega(n \lg n)
$$

thus $T(n) = \Omega(n \lg n)$

## Masters Theorem

The proof above was from first princibles, but we could instead use _masters theorem_.

Let $n_0 \in \mathbb{N}$, $k \in \mathbb{N}$, and $a, b \in \mathbb{R}$ with $a > 0$ and $b > 1$, let $T: \mathbb{N} \rightarrow \mathbb{N}$ satisfy the following recurrence:

$$
T(n) = \begin{cases}
\Theta(1) & n < n_0 \\
a \Theta\left(\frac{n}{b}\right) + \Theta(n^k) & n \geq n_0
\end{cases}
$$

Let the critical component $e = \log_b(a)$, then:

$$
T(n) = \begin{cases}
\Theta(n^e) & k < e \\
\Theta(n^e \lg n) & k = e \\
\Theta(n^k) & k > e \\
\end{cases}
$$

For merge sort we have the terms $a = 2$, $b = 2$, $k = 1$, $n_0 = 2$, thus $e = \log_2(2) = 1$. $k = e$ thus by case $II$ of Masters Theorem merge sort is $\Theta(n \lg n)$.

397e099910017317f6ac7799d4511aae85d0b626
ipynb
Jupyter Notebook
Merge Sort.ipynb
bens-notes/ads-notes
fdd273dd25e778551039a9f69740a8e1eaa641d8
MIT
Merge Sort.ipynb
bens-notes/ads-notes
fdd273dd25e778551039a9f69740a8e1eaa641d8
MIT
Merge Sort.ipynb
bens-notes/ads-notes
fdd273dd25e778551039a9f69740a8e1eaa641d8
MIT
Qwen/Qwen-72B
1. YES
2. YES