insertion sort is an algorithm that solves the sorting problem.

constituents

a sequence of \(n\) numbers \(\{a_1, \dots a_{n}\}\), called keys

intuition

Say you have a sorted list; sticking a new element into the list doesn’t change the fact that the list is sorted.

requirements

Insertion sort provides an ordered sequence \(\{a_1’, \dots a_{n}’\}\) s.t. \(a_1’ \leq \dots \leq a_{n}’\)

void insertion_sort(int length, int *A) {
    for (int j=1; j<length; j++) {
        int key = A[j];

        // insert the key correctly into the
        // sorted sequence, when appropriate
        int i = j-1;

        while (i > 0 && A[i] > key) { // if things before had
                                      // larger key
            // move them
            A[i+1] = A[i]; // move it down
            // move our current value down
            i -= 1;
        }

        // put our new element into the correct palace
        A[i+1] = key;
    }
}

This is an \(O\qty(n^{2})\) algorithm.

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.