Java 54: Sorting & Comparator Mechanics
easy⏱ 5 mincoursejava
El contrato de Comparator
compare(a, b) devuelve un int negativo si a debe ir antes de b, cero si son iguales en este orden, y positivo si a debe ir después de b. Debe ser un orden total: consistente, transitivo y antisimétrico. Un bug común es return a - b con ints — se desborda para valores grandes/negativos; prefiere Integer.compare(a, b).
Comparator<Person> byAge = Comparator.comparingInt(Person::age);
Comparator<Person> byAgeThenName =
byAge.thenComparing(Person::name);
list.sort(byAgeThenName); // stable multi-key sort
list.sort(byAge.reversed()); // descending by age
Estabilidad y por qué compone
Un sort estable nunca reordena elementos que el comparator considera iguales. Por eso puedes ordenar por una clave secundaria primero, luego por la primaria, y obtener un desempate correcto — o simplemente encadenar thenComparing. Insertion sort y TimSort son estables; un quicksort ingenuo no, por eso Arrays.sort usa quicksort de doble pivote solo para primitivos (donde la estabilidad es irrelevante) y TimSort para objetos.
Insertion sort estable con un Comparator
Escribe insertionSort(arr, cmp) que ordene in-place desplazando los elementos mayores a la derecha e insertando cada elemento en su lugar — usando cmp(a, b) en cada comparación. Cuenta comparaciones y desplazamientos. Ordena [5, 2, 9, 1, 5, 6] ascendente e imprime el resultado y los contadores. Luego ordena un array de {name, score} por score y confirma que dos scores iguales mantienen el orden de entrada (estabilidad).
Construye comparators, no escribas compare()
Prefiere la API de factory + combinadores: Comparator.comparing(extractorDeClave), .thenComparing(...), .reversed(), Comparator.nullsFirst(...). Se lee de arriba a abajo en orden de prioridad y evita escaleras de if artesanales. Recurre a un compare escrito a mano solo para lógica de orden genuinamente personalizada.
Quiz: ¿por qué no a - b para un comparator de int?
(a, b) -> a - b parece bien pero se desborda: si a = Integer.MAX_VALUE y b = -1, la resta envuelve a un número negativo, invirtiendo el orden. Usa siempre Integer.compare(a, b) (o Comparator.comparingInt), que es seguro ante overflow.