Vai vari nosaukt algoritmus, kuru asymptotiskā sarežģītība ir labāka nekā ātrās kārtošanas?

Ātrā kārtošana vidēji darbojas O(n log n) laikā, kas ir optimāla asymptotika salīdzināmo algoritmu gadījumā. Tomēr dažos gadījumos ir pieejami algoritmi ar labāku asymptotisko sarežģītību:

• Skaitīšanas kārtošana (Counting Sort) — O(n + k), kur k ir vērtību diapazons. Strādā ātrāk, ja k nav pārāk liels.
• Radix kārtošana (Radix Sort) — O(d * (n + k)), kur d ir ciparu skaits, k — skaitļu sistēmas bāze. Efektīva skaitļu vai virkņu kārtošanai.
• Apvienošanas kārtošana (Merge Sort) — garantēti O(n log n), stabila un paredzama.

Svarīgi: algoritmi ar labāku nekā O(n log n) sarežģītību nav balstīti uz elementu salīdzināšanu, bet izmanto papildu pieņēmumus par datiem (piemēram, ierobežotu vērtību diapazonu).