Estabilidad de la ordenación: qué garantiza y cuándo importa

Qué es

Una ordenación es estable cuando los elementos que se comparan como iguales conservan su orden relativo de entrada. El HOWTO de ordenación de Python indica que sus ordenaciones tienen garantizada la estabilidad. MDN señala que, desde ECMAScript 2019, la especificación exige que Array.prototype.sort sea estable. El paquete sort de Go documenta que Stable mantiene el orden original de los elementos iguales, a diferencia de Sort, que no garantiza ser estable. GNU sort dispone de --stable, que desactiva su comparación de último recurso sobre la línea completa. La estabilidad es una propiedad del algoritmo: merge sort, insertion sort y Timsort son estables; un quicksort o un heapsort simples no lo son.

Por qué importa

La estabilidad permite componer ordenaciones. Si se ordena por fecha y después, de forma estable, por estado, se obtienen filas agrupadas por estado con las fechas en orden dentro de cada grupo. Una tabla ordenable que se reordena en cada clic mantiene entre los empates el orden anterior en lugar de mezclarlos. El caso contrario es SQL: ORDER BY sobre una columna no única no promete nada sobre los empates, de modo que los resultados paginados pueden mostrar una fila dos veces o no mostrarla nunca, a menos que se añada una columna única como criterio de desempate.

Cómo aplicarlo

• Para ordenaciones por varias claves, es preferible una única clave compuesta (key=lambda r: (r.status, r.date)): una sola pasada y la intención queda a la vista. La alternativa, cuando las claves requieren direcciones distintas, es encadenar ordenaciones estables desde la clave menos significativa hasta la más significativa.
• En SQL, termina todo ORDER BY que se use para paginar con una columna única (ORDER BY created_at, id).
• Confía en la estabilidad solo donde la documentación la indique; busca esa palabra en la referencia de la biblioteca antes de depender de ella.
• reverse=True de Python mantiene los elementos iguales en su orden original, lo cual difiere de ordenar y luego invertir la lista.
• En la línea de comandos, añade -s a GNU sort cuando los empates deban conservar el orden del archivo, por ejemplo al ordenar un log por un campo.

Trampas

Las pruebas que comparan una salida ordenada con empates dependen tanto de la estabilidad como del orden de entrada; conviene que los datos esperados no tengan empates o ordenar con una clave completa. La colación según la configuración regional (LC_ALL) cambia el orden de la misma entrada entre equipos, así que fija la configuración regional en los scripts. Los algoritmos estables pueden necesitar memoria adicional (búferes de mezcla), lo que importa en arreglos en memoria muy grandes. La estabilidad no dice nada sobre si la función de comparación es consistente: un comparador inconsistente produce un orden indefinido en cualquier algoritmo.