Algoritmo de ordenación
Método para ordenar elementos según una regla de comparación — el problema más estudiado a fondo de toda la informática.
La ordenación basada en comparaciones no puede, demostrablemente, superar O(n log n), porque n elementos tienen n! ordenaciones posibles y cada comparación solo reduce el espacio de búsqueda a la mitad. Quicksort, mergesort y heapsort alcanzan todos ese límite con distintos compromisos en memoria, estabilidad y comportamiento en el peor caso. Algoritmos como el conteo (counting sort) y el radix sort escapan al límite al no comparar en absoluto, pero exigen que las claves sean enteros dentro de un rango conocido.
En la práctica, nadie escribe el suyo propio. Las bibliotecas estándar usan híbridos refinados durante décadas — introsort en C++ (quicksort que cambia a heapsort cuando la recursión se vuelve profunda), Timsort en Python y Java para objetos, quicksort resistente a patrones adversos en Rust. La pregunta interesante rara vez es qué algoritmo, sino qué comparación: el orden de colación de un texto difiere según el idioma, y un comparador inconsistente produce comportamiento indefinido, no simplemente el orden equivocado.