Ordenando Coleções Java

Ordenar uma coleção Java é uma operação com três pontos de entrada idiomáticos: Collections.sort(list), list.sort(comparator) e stream.sorted(). Os três compartilham o mesmo algoritmo subjacente — um mergesort estável e adaptativo (variante TimSort) com pior caso O(n log n) — e a mesma dependência de um tipo de elemento Comparable ou de um Comparator que você fornece. As diferenças estão em onde o resultado fica e como o local de chamada fica escrito.

Este capítulo é sobre listas. Conjuntos e mapas têm suas próprias formas de permanecer ordenados (TreeSet, TreeMap) — eles ordenam na inserção, não depois. Se você tiver um HashSet que deseja ordenar, o padrão convencional é new ArrayList<>(set) seguido de uma ordenação.

Os três pontos de entrada

Collections.sort(list) — o original

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

No lugar. Estável. Retorna void. Anterior ao Java 8 e ainda comum porque é óbvio de ler e antecede as alternativas. Internamente delega para list.sort em JDKs modernos.

list.sort(comparator) — o método de instância moderno

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

Adicionado no Java 8 diretamente em List<E>. Mesma semântica que Collections.sort — no lugar, estável, retorna void. A forma de instância permite que uma implementação de lista substitua o algoritmo se puder fazer melhor (ex.: LinkedList não faz isso, mas uma lista personalizada pode).

Use list.sort para novo código. É mais curto, fica melhor com referências de método e não requer importar Collections.

stream.sorted() — quando você quer uma nova sequência

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

Retorna uma nova stream ordenada — a entrada não é alterada. Use isso quando:

• A entrada é imutável (List.of(...)) e list.sort lançaria uma exceção.
• Você está construindo um pipeline de qualquer forma (map, filter, depois sort).
• Você não quer mutar a lista de origem.

O custo é uma alocação extra do resultado ordenado. Para listas curtas é negligenciável; para uma lista com um milhão de elementos, um Collections.sort mutando no lugar é mais barato do que um stream().sorted().toList() que copia tudo.

Ordenação natural vs comparador

Tanto Collections.sort(list) quanto list.sort(null) usam a ordenação natural do tipo de elemento, definida pela sua implementação de Comparable:

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

Se o tipo de elemento não implementa Comparable, você verá ClassCastException em tempo de execução — não um erro de compilação, porque o cast acontece dentro da ordenação. Passe um Comparator explicitamente para corrigir:

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

Qualquer Comparator do capítulo anterior se aplica — chave única, chaves encadeadas, invertido, seguro para null, entre outros.

Ordenação estável: elementos iguais mantêm sua ordem

TimSort é estável: se dois elementos são iguais sob o comparador, o que veio primeiro na entrada ainda vem primeiro na saída. É isso que permite que a ordenação por múltiplas chaves funcione como passes individuais compostos:

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

Após os dois passes, a lista é ordenada por age principalmente e por lastName dentro de cada grupo de idade. Ordenar em ordem inversa de prioridade — chave secundária primeiro, chave primária por último — é o truque que faz a ordenação em múltiplos passes funcionar. Na maioria das vezes você escreveria o comparador encadeado do capítulo anterior; esta é a alternativa legada.

Listas modificáveis vs não modificáveis

List.of(...), Collections.unmodifiableList(...) e Arrays.asList(array) retornam listas que você não pode ordenar no lugar. list.sort(...) chama list.set(i, x) internamente, e listas imutáveis lançam UnsupportedOperationException por causa disso.

Duas soluções:

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

Arrays.asList(...) é um caso especial: a lista é de tamanho fixo, mas as posições são modificáveis, então sort funciona. add/remove não funcionam.

Listas de primitivos e o custo do boxing

List<Integer> encapsula cada valor. Ordenar um milhão de Integers é muito mais lento do que ordenar um int[]. Se os dados são primitivos, prefira:

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

…e converta para uma lista se precisar depois. O mesmo padrão se aplica a long[], double[], char[]. Se você está ordenando por uma chave primitiva em objetos, use Comparator.comparingInt, comparingLong, comparingDouble para evitar boxing dentro do comparador:

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

Collections.sort é no lugar; às vezes você quer uma cópia

Se você quiser um resultado ordenado sem mutar a origem:

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

…ou a forma com stream:

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

Ambas funcionam. A primeira são duas linhas e zero custo de pipeline. A segunda é uma expressão. Escolha a que melhor se encaixa no código ao redor.

Ordenando um Map por valor

Mapas não têm um método sort — não há "posição" em um Map. O idioma é ordenar o conjunto de entradas em uma List e depois iterar sobre ela:

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

Se você precisa que o resultado seja um mapa que itera nessa ordem, colete em um LinkedHashMap — sua ordem de inserção é sua ordem de iteração:

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));

A sobrecarga de toMap com quatro argumentos permite escolher a implementação do mapa. Não pule isso — o padrão é HashMap, que destrói a ordem que você acabou de impor.

Um exemplo completo: ordenação no lugar, ordenação com stream, comparador encadeado, ordenando um mapa

O programa abaixo ordena uma lista no lugar, constrói uma cópia ordenada com stream().sorted(), aplica um comparador encadeado com uma chave secundária invertida, e então ordena um mapa por valor em um LinkedHashMap que itera na ordem ordenada.

O que observar na execução:

• A ordenação no lugar usou o comparador encadeado e produziu idade crescente com desempate por salário decrescente em uma única chamada. Sem necessidade de segundo passe.
• A forma com stream retornou uma nova lista ordenada e deixou o List.of de origem intocado. Esse é o padrão correto quando a entrada é imutável ou compartilhada.
• Chamar sort em uma lista imutável lançou UnsupportedOperationException. A ordenação é no lugar, e "no lugar" requer mutabilidade.
• A classificação do mapa ficou em um LinkedHashMap, então sua iteração corresponde à ordem de classificação. Se tivéssemos usado toMap com três argumentos, o resultado teria sido um HashMap e a ordem teria sido perdida.

O que vem a seguir

Agora você pode ordenar qualquer lista e produzir uma cópia ordenada sem mutar a origem. Pesquisa é a próxima operação — encontrar um elemento por predicado, por igualdade ou por busca binária em uma lista já ordenada. O próximo capítulo é Pesquisando Coleções Java.

Prática