merge sort is a Divide and Conquer algorithm for sorting.

intuition

1. take a list, and split in half
2. recursively, call merge sort in each half
3. merge them together using two pointer method (i.e. advance pointer when one is smaller than the other)

requirements

def merge(a,b):
    ptr1 = 0
    ptr2 = 1
    new = []
    # use two pointers, ...

def mergesort(a):
    n = len(a)
    if n <= 1:
        return a
    l = mergesort(a[0: n/2])
    r = mergesort(a[n/2: n])
    return merge(l,r)

additional information

correctness

Induction.

Hypothesis: every recursive call on an array of at most length i, mergesort works.

Non-Parametric Learning Algorithm

The memory usage of the algorithm grow linearly as a function of the size of the dataset \(n\).

Parametric Learning Algorithm

There’s a fixed set of parameters \(\theta_{i}\) that you learn once, which you then use to make predictions. You don’t need to keep the dataset around.

constituents

• a list of elements of length \(n\)
• all \(n\) elements are distinct

Speed is measured as a function of \(n\).

requirements

List becomes sorted

additional information

Divide and Conquer

Break problem into smaller sub-problems.

example: multiplication

Multiplying by powers of ten is easy, so we can break a multiplication into smaller groups.

For instance, we can break \(n\) digit integer into:

\begin{equation} [x_1, x_2, \dots, x_{\frac{n}{2}}] \times 10^{\frac{n}{2}} + [x_{\frac{n}{2}+1}, x_{\frac{n}{2}+2}, \dots] \end{equation}

Then we can multiply two large values by writing:

\begin{align} x \times y &= \qty(a \times 10^{\frac{n}{2}} + b ) \qty(c \times 10^{\frac{n}{2}} + d) \\ &= \qty(a \times c ) 10^{n} + \qty(a \times d + c \times b) 10^{\frac{n}{2}} + \qty( b \times d) \end{align}