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.

Base case: 1 element array is sorted.

Step: If IH holds for all \(0 < i < k\), then it holds for \(i=k\).

performance

\(\log n\) levels, merge each takes \(n\).