Merge sort es un ordenamiento divide-and-conquer, estable que se ejecuta en tiempo garantizado O(n log n). Divide el arreglo por la mitad, ordena cada mitad recursivamente y luego fusiona las dos mitades ordenadas.
Un elemento único ya está ordenado (caso base). Fusionar dos listas ordenadas es lineal, y realizamos log n niveles de fusión.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
return merge(left, right)
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it stable
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
merge_sort([5, 2, 4, 1, 3]) # -> [1, 2, 3, 4, 5]
Ideal cuando necesitas estabilidad u O(n log n) garantizado, y para listas enlazadas y ordenamiento externo de archivos enormes. La memoria adicional O(n) es su principal desventaja.
Merge sort garantiza O(n log n) independientemente de la entrada, a diferencia del peor caso O(n²) de quicksort.
Su estabilidad preserva el orden relativo de claves iguales, lo cual importa para ordenamiento multi-clave.
El paso de fusión es una primitiva reutilizable, y la estructura divide-and-conquer es un patrón que reutilizarás en todas partes.