Algoritmos de ordenamiento

Ordenar es poner los elementos en orden. Parece sencillo, pero cada algoritmo equilibra de forma muy distinta velocidad, memoria, estabilidad y simplicidad — por eso todo curso de algoritmos empieza aquí.

Comparación

Algoritmo	Mejor	Promedio	Peor	Memoria	Estable	En el lugar
Burbuja	n	n²	n²	1	sí	sí
Selección	n²	n²	n²	1	no	sí
Inserción	n	n²	n²	1	sí	sí
Shell	n log n	≈ n^1.25	n^1.5	1	no	sí
Mezcla	n	n log n	n log n	n	sí	no
Rápido	n log n	n log n	n²	log n	no	sí
Montículos	n log n	n log n	n log n	1	no	sí
Conteo	n + k	n + k	n + k	n + k	sí	no
Radix	d(n + b)	d(n + b)	d(n + b)	n + b	sí	no

Todas las complejidades son O(…). k es el rango de valores, d el número de dígitos, b la base (10).

Ideas clave

Los ordenamientos por comparación (de burbuja a montículos) solo preguntan "¿a es menor que b?". Cualquier algoritmo así necesita en el peor caso al menos ${\log }_{2}n!\approx n{\log }_{2}n$ comparaciones: hay $n!$ órdenes posibles y cada comparación, en el mejor de los casos, los divide a la mitad. Así que O(n log n) es lo mejor posible — mezcla y montículos lo alcanzan siempre, el rápido en promedio.

El ordenamiento por conteo y radix no comparan elementos: usan los propios valores como índices del array. Así superan n log n — pero solo funcionan con enteros (o claves que puedan convertirse en enteros).

Estabilidad — los elementos iguales conservan su orden original. Importa cuando se ordenan registros por una clave y luego por otra: ordena a las personas por nombre y después, de forma estable, por edad — las personas de la misma edad quedan en orden alfabético.

En el lugar — el algoritmo solo necesita O(1) (u O(log n)) de memoria adicional además del array.

Cuál elegir

Situación	Elige
Uso general, el más rápido en promedio	Rápido
Debe ser estable o garantizar n log n	Mezcla
n log n garantizado con memoria O(1)	Montículos
Arrays pequeños o casi ordenados	Inserción
Enteros en un rango pequeño	Conteo
Muchos enteros con pocos dígitos	Radix
Aprender lo básico	Burbuja, selección

En código JavaScript de producción, Array.prototype.sort (TimSort, un híbrido de mezcla e inserción) suele ser la opción correcta. Esta biblioteca muestra cómo funcionan los algoritmos clásicos y ofrece implementaciones fiables para cursos, experimentos y casos especiales.

Bibliografía

• Cormen — T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms, 4.ª ed., MIT Press, 2022. Capítulos 2, 6, 7, 8.
• Sedgewick — R. Sedgewick, K. Wayne. Algorithms, 4.ª ed., Addison-Wesley, 2011. Capítulo 2.
• Knuth — D. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2.ª ed., 1998.