Pessoal, que tipo de algoritmo o metodo sort implementado utiliza?
Pensando em análise de complexidade de tempo e de espaço, fiquei curioso para saber como ele faz isso debaixo dos panos.
Você está vendo a versão anterior da nova experiência da Alura que estamos preparando para você. Em breve, ela ganha uma identidade visual novinha totalmente pensada em potencializar seus estudos!
Solucionado
Pessoal, que tipo de algoritmo o metodo sort implementado utiliza?
Pensando em análise de complexidade de tempo e de espaço, fiquei curioso para saber como ele faz isso debaixo dos panos.
Olá Rodrigo, tudo bem com você?
Isso depende da versão do Java; até o Java 6, era utilizado um Merge sort modificado, onde o desempenho linearitmico O(n log n) era garantido. De acordo com a documentação do Java 6:
O algoritmo de ordenação é um mergesort modificado (no qual a fusão é omitida se o elemento mais alto na sublista inferior for menor do que o elemento mais baixo na sublista alta). Este algoritmo oferece desempenho n log (n) garantido. [...] Essa implementação copia a lista especificada em uma matriz, ordena a matriz e itera sobre a lista, redefinindo cada elemento da posição correspondente na matriz. Isso evita o desempenho n 2 log (n) que resultaria da tentativa de classificar uma lista encadeada.
No Java 7, aperfeiçoaram o método e agora o Timsort é utilizado em seu lugar. Ele é um híbrido derivado do Merge sort e do Insertion sort que requer muito menos comparações que n log(n) quando a lista está parcialmente ordenada, ao mesmo tempo que mantém a mesma performance do Merge sort em listas aleatórias e na análise de pior caso.
Nota de implementação: esta implementação é um mergesort estável, adaptável e iterativo que requer muito menos do que n log (n) comparações quando o array de entrada está parcialmente ordenado, enquanto oferece o desempenho de um mergesort tradicional quando o array de entrada está ordenado aleatoriamente. Se a matriz de entrada estiver quase ordenada, a implementação requer aproximadamente n comparações. Os requisitos de armazenamento temporário variam de uma pequena constante para matrizes de entrada quase ordenadas a n / 2 referências de objeto para matrizes de entrada ordenadas aleatoriamente.
Muito obrigado pela resposta completíssima, Thiago!