Não existe um algoritmo de classificação com todas as propriedades desejadas específicas?

No site Sorting Algorithms , é feita a seguinte reivindicação:

O algoritmo de classificação ideal teria as seguintes propriedades:

• Estável: chaves iguais não são reordenadas.
• Opera no local, exigindo espaço extra.$O(1)$
• No pior dos casos, comparações de teclas .$O(n\cdot\lg(n))$
• Na pior das hipóteses, swaps.$O(n)$
• Adaptável: acelera até quando os dados são quase classificados ou quando há poucas chaves exclusivas.$O(n)$

Não há algoritmo que possua todas essas propriedades e, portanto, a escolha do algoritmo de classificação depende do aplicativo.

Minha pergunta é: é verdade que

não existe um algoritmo de [classificação] que possua todas essas propriedades

e se sim, por que? O que há nessas propriedades que impossibilitam todas elas simultaneamente?

O WikiSort e o GrailSort são dois algoritmos razoavelmente recentes que fazem comparações de chaves estáveis ​​e no pior dos casos . Infelizmente, eu não os entendo o suficiente para saber se eles se aproximam de swaps de O ( n ) ou são adaptáveis, então não sei se eles violam as quarta e quinta condições que você tem.$O(n\ lg(n))$$O(n)$

Ao examinar o artigo "Mesclagem estável no local baseada em proporção", de Pok-Son Kim e Arne Kutzner vinculado à página do WikiSort GitHub, Kim e Kutzner afirmam ter uma operação de 'mesclagem' que é (WikiSort é uma variante do Mergesort), mas não tenho certeza se isso se traduz em WikiSort comO(n)swaps. Afirma-se que o GrailSort é mais rápido (na página do WikiSort GitHub), então eu poderia imaginar que é provável que ambos tenham o pior caso detroca deO(n)e sejam adaptáveis.$O( m (\frac{n}{m} + 1))$$O(n)$$O(n)$

Se alguém conseguir entender o WikiSort e / ou o GrailSort, eu os apreciaria também por responder minha pergunta em aberto sobre isso

O smoothsort de Dijkstra chega perto, mas não é estável.

Nenhum algoritmo conhecido satisfaz todas essas propriedades. Essas propriedades foram procuradas à medida que desenvolvemos mais algoritmos de classificação. Por exemplo, a classificação por bolhas (provavelmente o algoritmo de classificação mais primitivo) provavelmente não era estável na primeira implementação, mas foi projetada para ser estável, pois os cientistas da computação procuravam torná-la mais eficiente em implementações posteriores. Portanto, os cientistas da computação provavelmente escolheram as melhores características dos melhores algoritmos e, como resultado, você criou uma lista de todas essas características desejáveis. Na realidade, é difícil ter o melhor de todos os mundos em qualquer coisa. Não é impossível, mas possivelmente impossível com nossas arquiteturas atuais.

$O$$\Omega$$\Theta$

(Embora essa seja uma pergunta antiga, eu me deparei com ela e outras pessoas também.)

De fato, existe um algoritmo que satisfaz (1) - (4) e a segunda metade de (5), portanto chega muito perto do requisito acima. É descrito em [1] e combina vários truques inventados nas últimas décadas.

[1]: Franceschini, G. Teoria Comput Syst (2007) 40: 327. https://doi.org/10.1007/s00224-006-1311-1