

In [ ]:

    
%%HTML
<style>
.container { width:100% } 
</style>

Merge Sort

In order to sort a list $L$ using merge sort we proceed as follows:

If $L$ has less than two elements, then $L$ is already sorted. Therefore we have: $$ \#L < 2 \rightarrow \mathtt{sort}(L) = L $$
Otherwise, the list $L$ is split into two lists that have approximately the same size. These lists are sorted recursively. Then, the sorted lists are merged in a way that the resulting list is sorted: $$ #L \geq 2 \rightarrow \mathtt{sort}(L) =
```
  \mathtt{merge}\bigl(\mathtt{sort}\bigl(\texttt{L[:n//2]}\bigr),
  \mathtt{sort}\bigl(\texttt{L[n//2:]}\bigr)\bigr)
```
$$ Here, $\texttt{L[:n//2]}$ is the first part of the list, while $\texttt{L[n//2:]}$ is the second part. If the length of $L$ is even, both part have the same number of elements, otherwise the second part has one element more than the first part.



In [ ]:

    
def sort(L):
    n = len(L)
    if n < 2:
        return L
    L1, L2 = L[:n//2], L[n//2:]
    return merge(sort(L1), sort(L2))

We still need to specify how two sorted lists $L_1$ and $L_2$ are merged in a way that the resulting list is also sorted.

If the list $L_1$ is empty, the result is $L_2$: $$ \mathtt{merge}([], L_2) = L_2 $$
If the list $L_2$ is empty, the result is $L_1$: $$ \mathtt{merge}(L_1, []) = L_1 $$
Otherwise, $L_1$ must have the form $[x_1] + R_1$ and $L_2$ has the form $[x_2] + R_2$. Then there is a case distinction with respect to the comparison of $x$ and $y$:
- $x_1 \leq x_2$. In this case, we merge $R_1$ and $L_2$ and put $x_1$ at the beginning of this list: $$x_1 \leq x_2 \rightarrow \mathtt{merge}\bigl([x_1] + R_1, [x_2] + R_2\bigr) = \bigl[x_1\bigr] + \mathtt{merge}\bigl(R_1,[x_2] + R_2\bigr) $$
- $\neg (x_1 \leq x_2)$. In this case, we merge $L_1$ and $R_2$ and put $x_2$ at the beginning of this list: $$\neg (x_1 \preceq x_2) \rightarrow \mathtt{merge}\bigl([x_1] + R_1, [x_2] + R_2\bigr) = \bigl[x_2 \bigr] + \mathtt{merge}\bigl([x_1] + R_1, R_2\bigr) $$



In [ ]:

    
def merge(L1, L2):
    if L1 == []:
        return L2
    if L2 == []:
        return L1
    x1, R1 = L1[0], L1[1:]
    x2, R2 = L2[0], L2[1:]
    if x1 <= x2:
        return [x1] + merge(R1, L2)
    else:
        return [x2] + merge(L1, R2)



In [ ]:

    
sort([7, 8, 11, 12, 2, 5, 3, 7, 9, 3, 2])



In [ ]: