Algoritmos de Ordenación

¿Por qué O(n log n) es el límite teórico?

Para algoritmos basados en comparaciones, el límite inferior teórico es Ω(n log n). La razón: cualquier algoritmo de ordenación basado en comparaciones puede representarse como un árbol de decisión donde cada hoja es una permutación posible. Con n elementos hay n! permutaciones, y un árbol binario de altura h tiene como máximo 2ʰ hojas. Por lo tanto h ≥ log₂(n!) ≈ n log n (por la aproximación de Stirling).

¿Qué es Timsort?

Timsort (Tim Peters, 2002) detecta "runs" — subsecuencias ya ordenadas de forma natural en los datos — y las fusiona con una variante optimizada de Mergesort. Para runs muy cortos usa Insertion Sort. El resultado es que en datos del mundo real (que casi siempre tienen algún orden parcial) Timsort supera en práctica a Quicksort puro.

Radix Sort: más rápido que O(n log n)

Radix Sort no usa comparaciones: ordena por dígitos de menor a mayor significatividad usando Counting Sort en cada paso. Su complejidad es O(n·k) donde k es el número de dígitos. Para enteros de 32 bits con n elementos grandes, puede superar a Quicksort. No aplica a datos genéricos (solo enteros o strings fijos).

Estabilidad encadenada

Si necesitas ordenar por múltiples campos (p. ej., primero por apellido, luego por nombre), la técnica correcta es aplicar sorts estables en orden inverso: primero ordena por nombre (campo secundario), luego por apellido (campo primario). Al ser estable, el orden relativo del primer sort se preserva en el segundo.