Merge Sort

merge_sort.py

def merge(A, B):
    C = []
    while len(A) and len(B):
        a, b = A[0], B[0]
        if a <= b:
            C.append(A.pop(0))
        else:
            C.append(B.pop(0))
    while len(A):
        C.append(A.pop(0))
    while len(B):
        C.append(B.pop(0))
    return C


def merge_sort(A):
    """
    Sort an array A[0..n]
    
    Running time: 
    O(nlogn)
    
    T(n) = 2 * T(n/2) + O(n)
    d = 1, a = 2, b = 2
    so by master theorem
    d = logb(a)
    1 = log2(2) == 1 (O(n^d * log(n))
    """
    if len(A) == 1:
        return A
    midpoint = len(A) // 2
    B = merge_sort(A[:midpoint])
    C = merge_sort(A[midpoint:])
    return merge(B, C)