# 9 - Recursion (3) Merge Sort

merge(l1, l2):
    L = []
    while(l1.isNotEmpty() || l2.isNotEmpty()):
        if l1.isEmpty():
            l.append(l2.removeFirst())
        elif l2.isEmpty():
            l.append(l1.removeFirst())
        else:
            if l1.first() < l2.first():
                l.append(l1.removeFirst())
            else:
                l.append(l2.removeFirst())

mergesort(A) //A=a_1, a_2, ..., a_n is a list of integers to sort
             //A=a_1, ..., a_n in sorted order
    
    if len(A) <= 1: return A
    
    A1 = [a_1,...a_floor(n/2)] //first half of list
    A2 = [a_floor(n/2)+1,...,a_n] //second half of list
    
    l1 = mergesort(A1)
    l2 = mergesort(A2)
    L = merge(l1, l2)
    return L


**Proof of correctness by induction on length of list (n)**
Base cases: $n=0, n=1$ obviously correct
Assume mergesort(L) correctly sorts any list A of length $\{0,1,2,...,n-1\}$
Prove that it correclty sorts any list of length $n$
- $|A_1| = \lfloor\frac{n}{2}\rfloor < n$ for $n \geq 1$, so by the inductive hypothesis, $L_1$ is a sorted version of $A_1$
- $|A_2| = \lceil\frac{n}{2}\rceil < n$ for $n \geq 2$, so by the inductive hypothesis $L_2$ is a sorted version of $A_2$
- $L$ = Merge($L1$, $L2$) is a sorted version of $A$

**Proof of time complexity**
Let $f(n)$ be the worst case number of times the body of the while loop executes for any input list $L$ of length $n$
- Assume that $n=2^k$ for some integer $k$

**Proof by induction on $n$**
Claim: $f(n) = n log_2 n$ when $n = 2^k$
Base case: $n=1=2^0$, $f(1)=0=1\times0=1\times log_2 1$
Inductive step:
- Inductive hypothesis: $f(r) = r log_2 r$ for any $r \in \{2^0, 2^1, 2^2,...2^{k-1}\}$
- Prove for $n=2^k$ $k \geq 1$
- $f(n) = f(\frac{n}{2}) + f(\frac{n}{2}) + n = 2\times f(\frac{n}{2}) + n = 2\times f(2^{k-1}) + n$
- = $2 \times (\frac{n}{2} log \frac{n}{2}) + n$
- 
- = $n(log n - 1) + n$
- = $n log n - n + n$
- = $n log n$

QED

Visualization of this

###### tags: `COMP2804`,`Recursion`