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.