Kas saame nimetada algoritme, mille asümptootne keerukus on parem kui kiire sorteerimise oma?

Kiire sorteerimine töötab keskmiselt O(n log n) ajal, mis on optimaalne asümptootiline keerukus võrdlusalgoritmidele. Siiski on olemas algoritme, millel on parem asümptootiline keerukus teatud juhtudel:

• Loendamise sorteerimine (Counting Sort) — O(n + k), kus k on väärtuste vahemik. Töötab kiiremini, kui k ei ole liiga suur.
• Radix sorteerimine (Radix Sort) — O(d * (n + k)), kus d on numbrite arv, k on arvusüsteemi alus. Efektiivne arvude või stringide sorteerimisel.
• Ühinemise sorteerimine (Merge Sort) — garanteeritult O(n log n), stabiilne ja prognoositav.

Oluline: algoritmid, mille keerukus on parem kui O(n log n), ei põhine elementide võrdlemisel, vaid kasutavad täiendavaid eeldusi andmete kohta (näiteks piiratud väärtuste vahemik).