[Algorytmy] Sortowanie przez porównania kluczy, ograniczenie

[tukanik]

Cześć
Jak wiadomo, ograniczenie dolne na sortowanie to \(\displaystyle{ O(n \log n).}\) Wiadomo, że istnieją sortownia w czasie liniowym ( CountSort , RadixSort), ale one zakładają przypadek szczególny.
Stąd też wynika pytanie, skąd wynika dolne ograniczenie na sortowanie?

[Dasio11]

W dowodzie, jaki znam, zakłada się, że algorytm podejmuje decyzje tylko na podstawie porównań liniowych kombinacji danych. Następnie pokazuje się, że algorytm, który zawsze wykonuje mniej niż \(\displaystyle{ \Theta( n \log n )}\) porównań, nie może zawsze zwracać poprawnego wyniku.