Intro sort

Introsort ou introspective sort é um algoritmo de ordenação criado por David Musser em 1997. Ele começa com o quicksort e muda para o heapsort quando a profundidade da recursividade excede um nível baseado no (logaritmo do) número de elementos a ser classificados. É o melhor dos dois mundos, com um tempo de execução de pior caso de O(n log n) e desempenho prático comparável ao quicksort em conjuntos de dados típicos. Uma vez que ambos os algoritmos que utiliza são ordenações de comparação, ele também é uma ordenação por comparação. Em quicksort, uma das operações críticas é a escolha do pivô: o elemento em torno do qual a lista é particionada. O algoritmo mais simples de seleção do pivô é tomar o primeiro ou o último elemento da lista como o pivô, obtendo um comportamento pobre para o caso de entradas ordenadas ou quase totalmente ordenadas. A variante de Niklaus Wirth usa o elemento do meio para prevenir essas ocorrências, degenerando em O(n²) para seqüências inventadas. O algoritmo de seleção de pivô "mediana melhor-de-três" obtém a mediana do primeiro, médio e últimos elementos da lista; no entanto, mesmo que isso funcione bem em muitos exemplos do mundo real, ainda é possível inventar uma lista matadora de mediana melhor-de-três que irá causar desaceleração dramática de um quicksort com base nesta técnica de seleção do pivô. Essas contribuições poderiam potencialmente ser explorada por um agressor, por exemplo, enviar essa lista para um servidor de Internet para ordenação como um ataque de negação de serviço. Musser relatou que em uma seqüência ''matadora de mediana melhor-de-três de 100.000 elementos, o tempo de excução do introsort foi de 1/200 do que o do quicksort "mediana melhor-de-três". Musser também considerou o efeito sobre o cache da pequena ordenação atrasada de Sedgewick, onde pequenos intervalos são...