|
Author: Eduardo Enriquez
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])