Ordenar colecciones Java

Ordenar una colección Java es una operación con tres puntos de entrada idiomáticos: Collections.sort(list), list.sort(comparator) y stream.sorted(). Los tres comparten el mismo algoritmo subyacente — un mergesort estable y adaptativo (variante TimSort) con O(n log n) en el peor caso — y la misma dependencia en un tipo de elemento Comparable o en un Comparator que tú proveas. Las diferencias están en dónde vive el resultado y cómo se lee en el sitio de llamada.

Este capítulo trata sobre listas. Los sets y mapas tienen sus propias formas de mantenerse ordenados (TreeSet, TreeMap) — ordenan en la inserción, no después del hecho. Si tienes un HashSet que quieres ordenado, el patrón estándar es new ArrayList<>(set) seguido de un sort.

Los tres puntos de entrada

Collections.sort(list) — el original

Collections.sort(list);                  // natural ordering — list element type must implement Comparable
Collections.sort(list, comparator);       // explicit comparator

En lugar. Estable. Devuelve void. Es anterior a Java 8 y sigue siendo común porque se lee de forma obvia y precede a las alternativas. Internamente delega en list.sort en JDKs modernos.

list.sort(comparator) — el método de instancia moderno

list.sort(null);                          // natural ordering — null means "use Comparable"
list.sort(comparator);

Añadido en Java 8 directamente en List<E>. Misma semántica que Collections.sort — en lugar, estable, devuelve void. La forma de instancia permite que una implementación de lista sobrescriba el algoritmo si puede hacerlo mejor (por ejemplo, LinkedList no lo hace, pero una lista personalizada podría).

Usa list.sort para código nuevo. Es más corto, se lee mejor con referencias a métodos y no requiere importar Collections.

stream.sorted() — cuando quieres una nueva secuencia

List<Person> sorted = people.stream()
                            .sorted(Comparator.comparingInt(Person::age))
                            .toList();

Devuelve un nuevo stream ordenado — la entrada no se modifica. Úsalo cuando:

• La entrada es inmutable (List.of(...)) y list.sort lanzaría una excepción.
• De todos modos estás construyendo un pipeline (map, filter, luego sort).
• No quieres mutar la lista fuente.

El costo es una asignación adicional del resultado ordenado. Para listas cortas es insignificante; para una lista de un millón de elementos, un Collections.sort que muta en lugar es más barato que un stream().sorted().toList() que copia todo.

Orden natural vs comparador

Tanto Collections.sort(list) como list.sort(null) usan el orden natural del tipo de elemento, definido por su implementación de Comparable:

List<String> names = new ArrayList<>(List.of("carol", "alice", "bob"));
names.sort(null);                        // [alice, bob, carol]

Si el tipo de elemento no implementa Comparable, verás ClassCastException en tiempo de ejecución — no un error de compilación, porque el cast ocurre dentro del sort. Pasa un Comparator explícitamente para solucionarlo:

List<Person> people = new ArrayList<>(...);
people.sort(Comparator.comparing(Person::name));

Cualquier Comparator del capítulo anterior aplica — clave única, claves encadenadas, invertido, null-safe, todo.

Sort estable: los elementos iguales mantienen su orden

TimSort es estable: si dos elementos son iguales bajo el comparador, el que vino primero en la entrada sigue viniendo primero en la salida. Eso es lo que permite que el ordenamiento multi-clave funcione como pases individuales compuestos:

people.sort(Comparator.comparing(Person::lastName));     // first pass
people.sort(Comparator.comparingInt(Person::age));        // second pass — primary key wins, ties broken by previous order

Después de ambos pases, la lista está ordenada por age principalmente y por lastName dentro de cada grupo de edad. Ordenar en orden inverso de prioridad — clave secundaria primero, clave primaria al final — es el truco que hace que el ordenamiento en múltiples pases funcione. La mayoría de las veces escribirías el comparador encadenado del capítulo anterior; esta es la alternativa legacy.

Listas modificables vs no modificables

List.of(...), Collections.unmodifiableList(...) y Arrays.asList(array) devuelven listas que no puedes ordenar en lugar. list.sort(...) llama a list.set(i, x) internamente, y las listas inmutables lanzan UnsupportedOperationException desde allí.

Dos soluciones:

List<String> sorted = original.stream().sorted().toList();   // new immutable, sorted list
List<String> copy   = new ArrayList<>(original); copy.sort(null);

Arrays.asList(...) es un caso especial: la lista es de tamaño fijo pero los slots son modificables, así que sort funciona. add/remove no.

Listas primitivas y el costo del boxing

List<Integer> envuelve cada valor. Ordenar un millón de Integers es mucho más lento que ordenar un int[]. Si los datos son primitivos, prefiere:

int[] data = ...;
Arrays.sort(data);                       // primitive sort: cache-friendly, no boxing

…luego convierte a lista si la necesitas después. El mismo patrón aplica a long[], double[], char[]. Si ordenas por una clave primitiva sobre objetos, usa Comparator.comparingInt, comparingLong, comparingDouble para evitar el boxing dentro del comparador:

people.sort(Comparator.comparingInt(Person::age));     // unboxed key extraction

Collections.sort es en lugar; a veces quieres una copia

Si quieres un resultado ordenado sin mutar la fuente:

List<String> sortedCopy = new ArrayList<>(source);
sortedCopy.sort(null);

…o la forma con stream:

List<String> sortedCopy = source.stream().sorted().toList();

Ambas funcionan. La primera son dos líneas y sin sobrecarga de pipeline. La segunda es una expresión. Elige la que mejor encaje con el código circundante.

Ordenar un Map por valor

Los mapas no tienen un método sort — no hay "posición" en un Map. El idioma es ordenar el conjunto de entradas en una List y luego iterar sobre ella:

List<Map.Entry<String, Integer>> byCount = scores.entrySet().stream()
    .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
    .toList();

Si necesitas que el resultado sea un mapa que itere en ese orden, recoge en un LinkedHashMap — su orden de inserción es su orden de iteración:

LinkedHashMap<String, Integer> ordered = scores.entrySet().stream()
    .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
    .collect(Collectors.toMap(
        Map.Entry::getKey, Map.Entry::getValue,
        (a, b) -> a, LinkedHashMap::new));

La sobrecarga de toMap con cuatro argumentos te permite elegir la implementación del mapa. No la omitas — el valor predeterminado es HashMap, que destruye el orden que acabas de imponer.

Un ejemplo trabajado: sort en lugar, sort con stream, comparador encadenado, ordenar un mapa

El programa siguiente ordena una lista en lugar, crea una copia ordenada con stream().sorted(), aplica un comparador encadenado con una clave secundaria invertida y luego ordena un mapa por valor en un LinkedHashMap que itera en el orden ordenado.

Qué extraer de la ejecución:

• El sort en lugar recogió el comparador encadenado y produjo orden ascendente por edad con desempatadores descendentes por salario en una sola llamada. No se necesitó un segundo pase.
• La forma con stream devolvió una nueva lista ordenada y dejó la fuente List.of intacta. Ese es el patrón correcto cuando la entrada es inmutable o compartida.
• Llamar a sort en una lista inmutable lanzó UnsupportedOperationException. El sort es en lugar, y "en lugar" requiere mutabilidad.
• El ranking del mapa aterrizó en un LinkedHashMap, así que su iteración coincide con el orden de clasificación. Si hubiéramos usado toMap con tres argumentos, el resultado habría sido un HashMap y el orden se habría perdido.

Qué sigue

Ahora puedes ordenar cualquier lista y puedes producir una copia ordenada sin mutar la fuente. La búsqueda es la siguiente operación — encontrar un elemento por predicado, por igualdad o por búsqueda binaria en una lista ya ordenada. El siguiente capítulo es Buscar en colecciones Java.

Práctica