Java e .NET: Por que diferentes algoritmos de classificação são usados ​​por padrão?

Apenas querendo saber por que Javae .NET Frameworkusa algoritmo de classificação diferente por padrão.

Em Java, Array.Sort() usa o algoritmo Merge Sort por padrão e como Wikipedia.com diz:

Em Java, os métodos Arrays.sort () usam classificação de mesclagem ou uma classificação rápida ajustada, dependendo dos tipos de dados e, para eficiência da implementação, alterne para a classificação de inserção quando menos de sete elementos da matriz estiverem sendo classificados

No .NET Framework, a Classificação RápidaArray.Sort/List.Sort() usa o algoritmo de classificação padrão ( MSDN ):

List.Sort () usa Array.Sort, que usa o algoritmo QuickSort. Essa implementação executa uma classificação instável; isto é, se dois elementos forem iguais, sua ordem poderá não ser preservada. Por outro lado, uma classificação estável preserva a ordem dos elementos que são iguais.

Observando a excelente tabela "Comparação de algoritmos" , podemos ver que os dois algoritmos têm um comportamento bastante diferente das perspectivas de pior caso e uso de memória:

Ambas Javae .NETsão ótimas estruturas para o desenvolvimento de soluções corporativas, ambas possuem plataformas para desenvolvimento incorporado. Então, por que eles estão usando um algoritmo de classificação diferente por padrão, alguma opinião?

Por mais deterministas que sejam os computadores, a engenharia de computadores não é uma ciência exata. Duas pessoas, no mesmo domínio do problema, farão uma análise e desenvolverão duas soluções diferentes que satisfazem todas as restrições do problema. Pode ser difícil ou impossível determinar empiricamente qual deles é "melhor" no caso geral.

Meu palpite é que o .NET QuickSort está em camadas sobre algo nas APIs do MFC ou do Windows e provavelmente é herdado de versões muito mais antigas do Windows, nas quais a vantagem multiencadeada do MergeSort nem sequer era considerada para os computadores de Windows. o dia. ( EDIT: não é, embora os desenvolvedores da Microsoft sejam fanboys do QuickSort há muito tempo, como evidenciado por essa escolha de implementação de classificação desde o MS-DOS).

O Java, que não pode usar nenhuma implementação específica da plataforma porque o Java foi projetado do zero para ser completamente independente da plataforma, seguiu um caminho diferente. Quem sabe por que o MergeSort saiu por cima; meu palpite é que a implementação ganhou algum tipo de competição de desempenho em comparação com outros tipos criados pelos desenvolvedores, ou que um MergeSort no espaço O (n) ficou com a melhor aparência no papel em termos de melhor ou pior desempenho (O MergeSort não possui o calcanhar de Aquiles relacionado à seleção de elementos, como o QuickSort, e o melhor dos casos é uma lista quase ordenada, embora seja frequentemente o pior do QuickSort). Duvido que os benefícios de multithreading tenham sido considerados inicialmente, mas a implementação atual pode muito bem ser multithread.

Diferentes equipes de desenvolvimento em duas empresas diferentes chegaram a conclusões diferentes sobre o caso de uso usual de suas estruturas e componentes e decidiram implementar de acordo.

Essencialmente, cada empresa fez sua análise, analisou sua base de clientes e tomou diferentes decisões de acordo.

Você não pode esperar que análises de diferentes empresas e equipes, usando diferentes suposições e dados brutos, cheguem à mesma conclusão.

Esta questão está um pouco desatualizada, já que o Java agora usa o Timsort (a partir do Java 7)

Dos algoritmos específicos mencionados:

• O Quicksort tem desempenho desfavorável em O (n ^ 2), mas é um pouco mais leve / consome menos memória, oferecendo melhor desempenho em um caso típico.

• O Mergesort garante desempenho de pior caso em O (n log n), mas carrega um pouco mais de sobrecarga e requisitos de memória. Também é automaticamente estável (ou seja, mantém elementos iguais na mesma ordem).

Os designers de Java parecem, em geral, ser um pouco mais conservadores / focados na "coisa certa", por isso não é de surpreender que tenham escolhido o Mergesort entre os dois, pois oferece melhores garantias.

Não sabe por que a Microsoft escolheu o Quicksort, talvez eles os fizessem parecer melhores em alguns micro-benchmarks?