Python: merge sort. Ordenamiento de listas en complejidad log n

La idea es dividir el problema en partes pequeñas. En este caso el caso base o minimo es un lista con dos elementos. Si uno es mayor que otro los invierto. Así aplicando esta técnica y llamando a la funcion que evalua este pequeño caso por cada subdivision de nuestra lista original (recursivamente) conquistamos la resolución de todo el problema.

def merge(left, right):
    result = []

    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))

    return result + left + right

def merge_sort(alist):
    if len(alist) < 2:
        return alist

    mid = len(alist) / 2

    left = merge_sort(alist[:mid])
    right = merge_sort(alist[mid:])

    return merge(left, right)


print merge_sort([0, 22, 3, -1])Copy