Merge sort y quick sort: ordenar de verdad en O(n log n)
Ordenar como lo hacen los profesionales
Seguimos la serie de Algoritmos. En la entrega anterior vimos los tres métodos sencillos, todos O(n²), que se ahogan con muchos datos. Hoy llegan los que sí se usan en serio: merge sort y quick sort, los dos O(n log n).
Estos no son ejercicios de pizarra. Cuando llamas a la función de ordenar de tu lenguaje (el sort de cualquier sitio), por debajo está corriendo una versión de uno de estos dos, o una mezcla. Son la realidad de cómo se ordena en el mundo. Y los dos comparten una misma estrategia genial: divide y vencerás.
Divide y vencerás: la idea de fondo
Antes de los algoritmos, la estrategia. Divide y vencerás consiste en coger un problema grande, partirlo en problemas más pequeños del mismo tipo, resolver esos, y combinar las soluciones. Es una de las grandes formas de atacar problemas, y le dedicaremos su entrega entera cuando lleguemos a los paradigmas.
Para ordenar, la idea es: ordenar una lista enorme es difícil, pero ordenar listas pequeñas es fácil. Así que parte, parte y parte hasta que sea trivial, y luego recompón. Los dos algoritmos de hoy hacen esto, cada uno a su manera.
Merge sort: parte hasta el fondo y recompón
El merge sort (ordenación por mezcla) es el más metódico. Hace dos cosas:
- Divide: parte la lista por la mitad, y cada mitad por la mitad, una y otra vez, hasta tener trozos de un solo elemento. Una lista de un elemento ya está ordenada, claro.
- Mezcla (merge): va juntando esos trozos de dos en dos, mezclándolos de forma ordenada. Mezclar dos listas ya ordenadas es fácil: comparas los primeros de cada una, coges el menor, y repites.
FUNCION merge_sort(lista)
SI longitud(lista) <= 1 ENTONCES RETORNAR lista
medio = longitud(lista) / 2
izquierda = merge_sort(lista[0 .. medio])
derecha = merge_sort(lista[medio .. fin])
RETORNAR mezclar(izquierda, derecha)
FIN FUNCION
FUNCION mezclar(a, b)
resultado = lista vacía
MIENTRAS a y b tengan elementos
SI primero(a) <= primero(b) ENTONCES
mover primero(a) a resultado
SI NO
mover primero(b) a resultado
FIN SI
FIN MIENTRAS
añadir lo que quede de a y de b a resultado
RETORNAR resultado
FIN FUNCION
¿Por qué es O(n log n)? Porque partir la lista por la mitad sucesivamente crea log n niveles (como en la búsqueda binaria), y en cada nivel hay que mezclar n elementos en total. n por log n. Limpio y predecible.
El merge sort es estable y su rendimiento es siempre O(n log n), pase lo que pase con los datos. Su único pero: necesita memoria extra para las mezclas, no ordena del todo in-place. A cambio, es de una fiabilidad total.
Quick sort: elige un pivote y reparte
El quick sort (ordenación rápida) ataca distinto, y suele ser más rápido en la práctica a pesar de su nombre presuntuoso. Su jugada:
- Elige un elemento como pivote (por ejemplo, el último).
- Reparte (partition): coloca a la izquierda del pivote todos los menores y a la derecha todos los mayores. Tras esto, el pivote está en su posición definitiva.
- Repite el proceso, recursivamente, en la parte izquierda y en la derecha.
FUNCION quick_sort(lista, inicio, fin)
SI inicio >= fin ENTONCES RETORNAR
p = repartir(lista, inicio, fin) // coloca el pivote y devuelve su posición
quick_sort(lista, inicio, p - 1)
quick_sort(lista, p + 1, fin)
FIN FUNCION
En el caso medio es O(n log n), y con muy buena constante (de ahí que sea tan rápido). Además ordena in-place, casi sin memoria extra. Por eso es el favorito de tanta gente.
El talón de Aquiles del quick sort
Pero tiene una trampa. Su rendimiento depende de elegir buenos pivotes. Si tienes mala suerte (o malicia) y el pivote acaba siendo siempre el mayor o el menor, los repartos quedan totalmente desequilibrados y el algoritmo degenera a O(n²), igual de lento que un bubble sort. El caso clásico que lo dispara: una lista que ya está ordenada y eliges como pivote el primer o último elemento.
¿La solución? Elegir el pivote con cabeza: al azar, o la mediana de tres elementos. Con eso, el peor caso se vuelve tan improbable que en la práctica no aparece. Pero conviene saber que está ahí, porque es justo el tipo de detalle que te preguntan en una entrevista.
La frontera del O(n log n)
Aquí va un dato que sorprende: ningún algoritmo que ordene comparando elementos puede bajar de O(n log n) en el peor caso. Está demostrado matemáticamente, es un límite teórico. Así que merge sort y quick sort no es que sean buenos: es que rozan lo máximo posible para su categoría.
¿Significa eso que no se puede ordenar más rápido? Curiosamente, sí se puede, pero solo haciendo trampa: dejando de comparar. De eso va la próxima entrega, la ordenación no comparativa.
Qué usa cada lenguaje por dentro
Por curiosidad práctica, esto es lo que hacen los lenguajes de verdad cuando ordenas:
- Muchos usan Timsort, un híbrido de merge sort e insertion sort diseñado para aprovechar trozos que ya vienen ordenados. Es lo que hay detrás del
sortde varios lenguajes muy populares. - Otros usan introsort, que empieza con quick sort y cambia a otro método si detecta que está degenerando al peor caso.
Fíjate en el detalle: los profesionales que escriben estas librerías no eligen un solo algoritmo, combinan varios para quedarse con lo mejor de cada uno. Esa es la mentalidad que da entender los algoritmos.
Un apunte sobre la estabilidad
Un matiz más para elegir entre los dos: el merge sort es estable (no altera el orden relativo de los elementos iguales) y el quick sort, en su forma habitual, no lo es. Si ordenas por varios criterios encadenados, esa estabilidad importa, y es una razón más para preferir el merge sort en ciertos casos, aunque el quick sort sea más rápido de media.
El libro para esta entrega
El quick sort tiene un capítulo entero, dibujado y explicado con calma, en Comprender los algoritmos, de Aditya Bhargava, donde además aprovecha para explicar bien el divide y vencerás. Para esta entrega, es justo lo que necesitas.
Lo siguiente: romper la barrera
Hemos visto que O(n log n) es lo mejor posible… si ordenas comparando. Pero, ¿y si no comparas? Resulta que en algunos casos concretos se puede ordenar en tiempo lineal, O(n), rompiendo la supuesta barrera.
En la próxima entrega vemos cómo lo consiguen el counting, el radix y el bucket sort, y qué precio hay que pagar a cambio de esa velocidad.
Preguntas frecuentes
¿Qué es mejor, merge sort o quick sort?
Depende. El quick sort suele ser más rápido en la práctica y ordena in-place (casi sin memoria extra), pero tiene un peor caso O(n²) si los pivotes salen mal. El merge sort es siempre O(n log n) pase lo que pase, y es estable, pero necesita memoria adicional. Para fiabilidad total, merge sort; para velocidad media con buena elección de pivote, quick sort.
¿Por qué el quick sort puede ser O(n²) si se supone que es rápido?
Porque su rendimiento depende de elegir buenos pivotes que repartan la lista en mitades equilibradas. Si el pivote acaba siendo siempre el mayor o el menor (por ejemplo, en una lista ya ordenada eligiendo el primer elemento), los repartos quedan desbalanceados y degenera a O(n²). Se evita eligiendo el pivote al azar o como mediana de tres, lo que hace ese peor caso muy improbable.
¿Se puede ordenar más rápido que O(n log n)?
Comparando elementos, no: O(n log n) es un límite teórico demostrado para cualquier algoritmo de ordenación por comparación. Sin embargo, sí se puede ordenar en tiempo lineal O(n) con algoritmos que no comparan, como counting sort o radix sort, a cambio de exigir condiciones especiales sobre los datos (rango acotado, valores enteros). Es el tema de la siguiente entrega.
Este artículo contiene enlaces de afiliado.
Compártelo si te ha resultado útil.
¿Sabías que el sort de tu lenguaje favorito combina varios algoritmos por dentro? Cuéntame cuál usas.
Y… en la próxima entrega, ordenamos sin comparar.
Artículos relacionados
Ordenamiento sencillo: bubble, selection e insertion sort
Ordenar una colección es uno de los problemas más estudiados de la informática, y empezamos por los tres algoritmos sencillos: bubble sort, selection sort e insertion sort. Son lentos, los tres O(n²), y ninguno se usa en serio con muchos datos. Pero son los que se entienden a la primera, los que te enseñan de verdad qué significa ordenar y los que ponen los cimientos para los métodos rápidos que vienen después. En esta tercera entrega de la serie de Algoritmos te explico cómo funciona cada uno paso a paso, por qué los tres son O(n²), qué es la estabilidad y el ordenar in-place, y por qué el insertion sort, el patito feo, gana cuando los datos están casi ordenados. Con pseudocódigo y el intercambio visto paso a paso.
Búsqueda lineal vs binaria: el poder de partir por la mitad
Buscar algo en una colección es el problema más cotidiano de la programación, y hay dos formas de hacerlo que no se parecen en nada. La búsqueda lineal mira uno a uno, de principio a fin: simple, funciona siempre, pero lenta. La búsqueda binaria parte la colección por la mitad una y otra vez y encuentra lo que buscas en un puñado de pasos, aunque haya millones de elementos. En esta segunda entrega de la serie de Algoritmos te explico las dos, su complejidad (O(n) frente a O(log n)), el requisito imprescindible de la binaria, sus versiones iterativa y recursiva, y cuándo usar cada una. Verás en acción esa diferencia brutal entre mirar un millón de cosas o solo veinte.
Qué es un algoritmo y la notación Big-O explicada paso a paso
Arranca la serie de Algoritmos, y lo hace por donde hay que empezar: aprendiendo a medir. Antes de comparar dos formas de resolver un problema necesitas saber cuál es mejor, y para eso está la notación Big-O. En esta primera entrega te explico qué es un algoritmo de verdad, qué es la complejidad temporal y espacial, y cómo leer esa notación que da tanto respeto: O(1), O(log n), O(n), O(n log n), O(n²) y la temida O(2^n). Lo verás con ejemplos cotidianos, sin matemáticas asustaviejas, y entenderás de una vez por qué un algoritmo puede tardar una décima de segundo y otro, con los mismos datos, dejarte el ordenador colgado una hora. Esto es la regla con la que se mide todo lo que viene después.