Por que Collections.sort usa merge sort em vez de quicksort?

Sabemos que a classificação rápida é o algoritmo de classificação mais rápido.

O JDK6 collections.sortusa o algoritmo de classificação por mesclagem em vez da classificação rápida. Mas Arrays.sort usa um algoritmo de classificação rápida.

Qual é o motivo pelo qual Collections.sort usa classificação por mesclagem em vez de classificação rápida?

Muito provável de Josh Bloch § :

Eu escrevi esses métodos, então suponho que estou qualificado para responder. É verdade que não existe um único algoritmo de classificação melhor. QuickSort tem duas deficiências principais quando comparado ao mergesort:

1. Não é estável (como observou parsifal).

2. Não garante n log n desempenho; pode degradar para desempenho quadrático em entradas patológicas.

A estabilidade não é um problema para os tipos primitivos, pois não há noção de identidade como distinta de (valor) igualdade. E a possibilidade de comportamento quadrático não foi considerada um problema na prática para a implementação de Bentely e McIlroy (ou posteriormente para Dual Pivot Quicksort ), razão pela qual essas variantes QuickSort foram usadas para os tipos primitivos.

A estabilidade é um grande problema ao classificar objetos arbitrários. Por exemplo, suponha que você tenha objetos representando mensagens de e-mail e os classifique primeiro por data e, em seguida, por remetente. Você espera que eles sejam classificados por data em cada remetente, mas isso só será verdade se a classificação for estável. É por isso que optamos por fornecer uma classificação estável (Merge Sort) para classificar as referências do objeto. (Tecnicamente falando, várias classificações sequenciais estáveis ​​resultam em uma ordem lexicográfica nas chaves na ordem inversa das classificações: a classificação final determina a subchave mais significativa.)

É um bom benefício colateral que Merge Sort garante desempenho n log n (tempo), independentemente da entrada. Claro que há um lado negativo: a classificação rápida é uma classificação "no local": ela requer apenas log n espaço externo (para manter a pilha de chamadas). Mesclar, classificar, por outro lado, requer espaço externo O (n). A variante TimSort (introduzida no Java SE 6) requer substancialmente menos espaço (O (k)) se a matriz de entrada estiver quase classificada.

Além disso, o seguinte é relevante:

O algoritmo usado por java.util.Arrays.sort e (indiretamente) por java.util.Collections.sort para classificar as referências do objeto é um "mergesort modificado (em que a fusão é omitida se o elemento mais alto na sublista inferior for menor que o elemento mais baixo na sublista superior). " É uma classificação estável razoavelmente rápida que garante o desempenho de O (n log n) e requer O (n) espaço extra. Em sua época (foi escrito em 1997 por Joshua Bloch), foi uma boa escolha, mas hoje podemos fazer muito melhor.

Desde 2003, a classificação de lista do Python usa um algoritmo conhecido como timsort (em homenagem a Tim Peters, que o escreveu). É um mergesort estável, adaptável e iterativo que requer muito menos do que n log (n) comparações ao ser executado em arrays parcialmente classificados, enquanto oferece desempenho comparável a um mergesort tradicional quando executado em arrays aleatórios. Como todos os mergesorts apropriados, o timsort é estável e roda em tempo O (n log n) (pior caso). No pior caso, timsort requer espaço de armazenamento temporário para n / 2 referências de objeto; na melhor das hipóteses, requer apenas uma pequena quantidade constante de espaço. Compare isso com a implementação atual, que sempre requer espaço extra para n referências de objeto e supera n log n apenas em listas quase classificadas.

Timsort é descrito em detalhes aqui: http://svn.python.org/projects/python/trunk/Objects/listsort.txt .

A implementação original de Tim Peters é escrita em C. Joshua Bloch a portou de C para Java e testou, comparou e ajustou extensivamente o código resultante. O código resultante é uma substituição instantânea para java.util.Arrays.sort. Em dados altamente ordenados, esse código pode ser executado até 25 vezes mais rápido que a implementação atual (na VM do servidor HotSpot). Em dados aleatórios, as velocidades das implementações antigas e novas são comparáveis. Para listas muito curtas, a nova implementação é substancialmente mais rápida que a antiga, mesmo em dados aleatórios (porque evita a cópia desnecessária de dados).

Além disso, consulte Java 7 usando Tim Sort para o método Arrays.Sort? .

Não existe uma única escolha "melhor". Como acontece com muitas outras coisas, trata-se de compensações.