Czy nie ma algorytmu sortowania ze wszystkimi konkretnymi pożądanymi właściwościami?

Na stronie internetowej Sorting Algorytmy wysunięto następujące oświadczenie:

Idealny algorytm sortowania miałby następujące właściwości:

• Stabilny: nie zmienia się kolejności klawiszy równych.
• Działa w miejscu, wymagając dodatkowej przestrzeni.$O(1)$
• Porównania klawiszy w najgorszym przypadku .$O(n\cdot\lg(n))$
• Zamiany najgorszym przypadku .$O(n)$
• Adaptacyjny: Przyspiesza do gdy dane są prawie posortowane lub gdy istnieje kilka unikalnych kluczy.$O(n)$

Nie ma algorytmu, który posiadałby wszystkie te właściwości, dlatego wybór algorytmu sortowania zależy od aplikacji.

Moje pytanie brzmi: czy to prawda?

nie ma algorytmu [sortowania], który posiadałby wszystkie te właściwości

a jeśli tak, to dlaczego? Co takiego jest w tych właściwościach, że uniemożliwia spełnienie wszystkich z nich jednocześnie?

WikiSort i GrailSort to dwa dość nowe algorytmy, które stosują stabilne, najgorsze porównania . Niestety nie rozumiem ich wystarczająco dobrze, aby wiedzieć, czy zbliżają się do zamiany czy też są adaptacyjne, więc nie wiem, czy naruszają czwarty i piąty warunek, jaki masz.O ( n $O(n\ lg(n))$$O(n)$

Patrząc na artykuł „Łączenie stabilnych miejsc w oparciu o współczynnik”, autorstwa Pok-Son Kim i Arne Kutznera, do których prowadzi strona WikiSort GitHub, Kim i Kutzner twierdzą, że mają operację „scalania”, która jest (WikiSort jest odmianą Mergesort), ale nie jestem pewien, czy to przekłada się na WikiSort z zamianami . Uważa się, że GrailSort jest szybszy (na stronie GitHub WikiSort), więc mogę sobie wyobrazić, że prawdopodobnie oba mają najgorszy przypadek zamiany i są adaptacyjne.O(n)O(n$O( m (\frac{n}{m} + 1))$$O(n)$$O(n)$

Jeśli komuś uda się zrozumieć WikiSort i / lub GrailSort, byłbym wdzięczny za odpowiedź na moje otwarte pytanie na ten temat

Dijkstry smoothsort zbliża, ale nie jest stabilna.

Żadne znane algorytmy nie spełniają wszystkich tych właściwości. Te właściwości stały się poszukiwane, gdy opracowaliśmy więcej algorytmów sortowania. Na przykład sortowanie bąbelkowe (prawdopodobnie najbardziej prymitywny algorytm sortowania), najprawdopodobniej było niestabilne w pierwszej implementacji, ale zostało zaprojektowane tak, aby było stabilne, ponieważ informatycy starali się zwiększyć jego wydajność w późniejszych implementacjach. Informatycy najprawdopodobniej wybrali najlepsze cechy z najlepszych algorytmów, w wyniku czego powstała lista wszystkich tych pożądanych cech. W rzeczywistości trudno mieć w sobie wszystko, co najlepsze. Nie jest to niemożliwe, ale możliwe, że niemożliwe przy naszych obecnych architekturach.

PS Użyj Big-O ( ) jako asymptotycznej górnej granicy, a Big-Omega ( ) jako asymptotycznej dolnej granicy. Theta ( ) pomiędzy.Ω $O$$\Omega$$\Theta$

(Chociaż jest to stare pytanie, natknąłem się na to, podobnie jak inni).

Rzeczywiście istnieje algorytm, który spełnia (1) - (4) i drugą połowę (5), więc jest bardzo zbliżony do powyższego wymogu. Jest opisany w [1] i łączy w sobie kilka sztuczek wynalezionych w ciągu ostatnich dziesięcioleci.

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