Merge Sort

1. divide and conquer
2. recursive
3. stable
4. not in-place

complexity

T(n) = 2T(n/2) + c'n + c''
        = 4T(n/4) + 2c'n ...
        = 8T(n/8) + 3c'n ...
        = ....
        = 2^k * T(n/(^k)2) + 2*c'n
        = 2^(logN) T(1) + log(n) c' * n
        = nc + c' nlogn

time: O(nlogn)

space

• if not clear for each level O(nlogn)
• if clear after merge is done O(2n) = O(n)

def mergeSort(A):
    length = len(A)
    if length < 2:
        return A
    mid = length / 2
    left = A[:mid]
    right = A[mid:]
    left = self.mergeSort(left)
    right = self.mergeSort(right)

    return mergeI(left, right)

def merge(left, right):
    # merge 2 sorted list