Ar galite paminėti algoritmus, kurių asimptotinė sudėtingumas yra geresnis nei greitojo rūšiavimo?

Greitasis rūšiavimas vidutiniškai veikia O(n log n) laiku, tai yra optimalus asimptotinis laikas lyginamosioms algoritmams. Tačiau tam tikrais atvejais yra algoritmų su geresne asimptotine sudėtingumu:

• Skaičiavimo rūšiavimas (Counting Sort) — O(n + k), kur k yra reikšmių diapazonas. Veikia greičiau, jei k nėra per didelis.
• Radix rūšiavimas (Radix Sort) — O(d * (n + k)), kur d yra skaitmenų skaičius, k — skaičių sistemos pagrindas. Efektyvus skaičių ar eilutės rūšiavimui.
• Sujungimo rūšiavimas (Merge Sort) — garantuotas O(n log n), stabilus ir prognozuojamas.

Svarbu: algoritmai, turintys geresnį nei O(n log n) sudėtingumą, nesiremia elementų palyginimu, o naudoja papildomas prielaidas apie duomenis (pavyzdžiui, ribotą reikšmių diapazoną).