El ordenamiento por mezcla (merge sort) en Python
En esta lección vas a implementar el ordenamiento por mezcla con la estrategia divide y vencerás, usando una función recursiva.
Introducción
El problema
Los ordenamientos sencillos se vuelven muy lentos cuando las listas crecen: duplicar los datos cuadruplica el trabajo. El ordenamiento por mezcla divide el problema en problemas más pequeños y fáciles de resolver, y hace que el trabajo crezca solo un poco más rápido que los datos.
Imagínalo así
El ordenamiento por mezcla es como ordenar un gran montón de exámenes con amigos. Divides el montón en dos, das cada mitad a alguien, y cada uno vuelve a dividir el suyo, hasta que todos tienen un solo examen. Luego, por parejas, mezclan sus montones ordenados tomando siempre el examen de arriba más pequeño, hasta que queda un único montón ordenado.
if len(values) <= 1:📄 Un solo examen ya está ordenadomerge_sort(values[:middle])✂️ Divide el montón y ordena cada mitadleft[left_index] <= right[right_index]🤝 Mezcla: toma el examen de arriba más pequeñoresult + left[left_index:] + right[right_index:]📚 Añade lo que quede del otro montónEl ordenamiento por mezcla divide una lista en dos, ordena cada mitad de forma recursiva y mezcla las dos mitades ordenadas. Tarda O(n log n).
Puntos clave
if len(values) <= 1: return valueses el caso base que detiene la recursión.merge_sort(values[:middle])ymerge_sort(values[middle:])ordenan las dos mitades.- El bucle
whiletoma el valor delantero más pequeño delefto derighthasta que una de las listas se acaba. left[left_index:]yright[right_index:]añaden los valores que quedan, que ya están ordenados.<=toma primero de la izquierda en caso de empate, lo que mantiene los valores iguales en su orden original.
¿Cuándo se usa?
- Ordenar grandes cantidades de datos con una velocidad predecible, sin un peor caso lento.
- Ordenar listas enlazadas o datos demasiado grandes para la memoria (ordenación externa).
- Aprender divide y vencerás, un patrón que usan muchos algoritmos.
Cuándo no hace falta
- Código Python normal:
sorted()ya usa Timsort, una mezcla afinada de ordenamiento por mezcla e inserción. - Memoria muy justa: el ordenamiento por mezcla necesita espacio extra para las listas mezcladas.
Visualizador de El ordenamiento por mezcla (merge sort) en Python
O(n log n)Usa Reproducir o Paso para seguir cada comparación y movimiento de datos.
Código de ejemplo
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Resultado de la ejecución
[3, 9, 10, 27, 38, 43, 82]
Explicación del código
La función recursiva divide la lista hasta que cada trozo tiene un solo elemento, porque una lista de un elemento siempre está ordenada. Después, el bucle while mezcla las dos sublistas tomando siempre el menor de los dos elementos del principio. El algoritmo se ejecuta siempre en O(n log n) y necesita O(n) de memoria adicional.
Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.
Ejercicios de práctica
Prueba a modificar el código siguiendo las ideas de abajo. Cambiar el código y ver el resultado te ayudará a entender la lección mucho mejor que solo leerla.
- Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
- Muestra el estado después de cada paso para ver el algoritmo en acción.
- Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Errores comunes
Olvidar los elementos que sobran
Cuando una mitad se acaba, el resto de la otra mitad se pierde.
return result
return result + left[left_index:] + right[right_index:]
¿Terminaste esta lección?
Márcala como aprendida para seguir tu progreso.
Practica con un reto
Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.
Todos los retos